A comprovação de DOUBLE-SAT é NP-complete

13

O conhecido problema SAT é definido aqui para fins de referência.

O problema DOUBLE-SAT é definido como

DOUBLE-SAT={ϕϕ has at least two satisfying assignments}

Como provamos que é NP-completo?

Mais de uma maneira de provar será apreciada.

pnp
fonte

Respostas:

25

Aqui está uma solução:

Claramente, Double-SAT pertence a , uma vez que um NTM pode decidir Double-SAT da seguinte maneira: Em uma fórmula de entrada booleana ϕ ( x 1 , , x n ) , adivinhe 2 de forma não-determinística e verifique se ambos satisfazem ϕ .NPϕ(x1,,xn)ϕ

Para mostrar que a Double-SAT é -Complete, que dão uma redução de sab em Double-sab, como segue:NP

Na entrada :ϕ(x1,,xn)

  1. Introduzir uma nova variável .y
  2. Fórmula de saída .ϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯)

Se pertence a SAT, então ϕ tem pelo menos 1 tarefa satisfatória e, portanto, ϕ ' ( x 1 , , x n , y ) possui pelo menos 2 tarefas satisfatórias, pois podemos satisfazer a nova cláusula ( y ˉ y ) atribuindo y = 1 ou y = 0 à nova variável y , então ϕ ( xϕ(x1,,xn)ϕϕ(x1,,xn,y)yy¯y=1y=0yϕ , ..., x n , y ) SAT duplo.x1xny

Por outro lado, se , então claramente ϕ ( x 1 , , x n , y ) = ϕ ( x 1 , , x n ) ( y ˉ y ) também não possui atribuição satisfatória, então ϕ ( x 1 , , xϕ(x1,,xn)SATϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯) .ϕ(x1,,xn,y)Double-SAT

Portanto, , e, portanto, duas vezes SAT é N P -Complete.SATpDouble-SATNP

pnp
fonte
Isso é melhor do que a minha proposta.
Raphael
10

Você sabe que é NP-completo. Você pode encontrar uma redução de S A T para D O U B L E - S A T ? Ou seja, você pode manipular uma fórmula satisfatória para que o resultado tenha pelo menos duas atribuições satisfatórias? Observe que a mesma manipulação não pode tornar satisfatórias as fórmulas não confiáveis.SATSATDOUBLE-SAT

Para qualquer fórmula , a fórmula φ f ( φ ) tem, pelo menos, duas vezes o número de satisfazer assingments como φ , com f um homomorphism que renomeia todas as variáveis para novos nomes.φφf(φ)φf

Rafael
fonte