como você prova que o SAT é NP-completo?

7

Como é, como você prova que o SAT é NP-completo?

Eu sei o que significa NP-complete, então não preciso de uma explicação sobre isso.

O que eu quero saber é como você sabe que um problema, como o SAT, é NP-completo sem recorrer à redução de outros problemas, como o problema hamiltoniano ou o que seja.

complexity-theory satisfiability user2346
fonte
11
postado cruzadamente
user2346 8/12/12
11
Então, em particular, a redução original do SAT não é uma resposta para sua pergunta? (Por favor, não faça perguntas cruzadas. Se a pergunta não fosse mais ontópica aqui do que em math.SE, eu encerraria imediatamente.)
Raphael
@ Rafael Encontrei uma resposta .. Obrigado pela ajuda de qualquer maneira. Percebi que o SAT deveria ser considerado antes do 3-SAT, pois a NP-3 pode ser conhecida pelo processo de redução do SAT.
User2346 8/12/12
@ user2346 Got aqui muito tarde, aparentemente
Lucas Cozinhe
3
Não poste a mesma pergunta em vários sites do Stack Exchange.
Gilles 'SO- stop be evil'

Respostas:

15

Acredito que o 3-SAT foi originalmente reduzido da SATISFIABILIDADE mais geral do artigo de Karp, que delineava 21 problemas completos de NP .

A Wikipedia tem uma descrição de como mostrar que SATISFIABILITY é NP-complete, um resultado conhecido como teorema de Cook-Levin . A idéia dessa prova é mostrar que qualquer máquina de Turing não determinística no tempo polinomial pode ser modelada como uma expressão booleana com tamanho polinomial. A expressão booleana possui termos para representar o espaço de configuração válido da máquina de Turing: onde está a cabeça da fita, qual é o estado atual, quais símbolos estão escritos na fita e quais transições são válidas em todas as posições. Como o NTM será interrompido no tempo polinomial, o espaço de configuração é limitado e podemos fazer uma expressão polinomial (grande) para representá-lo.

Lucas Cook
fonte
9
Quão apropriado é que um cozinheiro dê essa resposta.
Raphael
@Raphael Heh, nenhuma relação (tanto quanto eu sei!) #
Lucas Cook #
O 3SAT já está no artigo original de Steve Cook.
precisa