come si fa a dimostrare che SAT è NP-completo?

Question

Come è, come si fa a dimostrare che SAT è NP-completo?

Lo so che cosa intende per NP-completo, quindi non ho bisogno di una spiegazione su questo.

Quello che voglio sapere è come si fa a sapere che uno dei problemi, come ad esempio SAT, è NP-completo senza ricorrere alla riduzione ad altri problemi come problema di Hamilton o qualsiasi altra cosa.

Answer 1

Credo 3-SAT è stato originariamente ridotto dal soddisfacibilità più generale in carta di Karp, che ha delineato problemi 21 NP-completi .

Wikipedia ha una descrizione di come per dimostrare che soddisfacibilità è NP-completo, un risultato che è noto come il Cook-Levin teorema . L'idea di questa prova è quello di mostrare che ogni volta che la macchina non deterministica di Turing polinomio può essere modellato come un'espressione booleana con la dimensione polinomiale. L'espressione booleana deve termini per rappresentare lo spazio configurazione valida della macchina di Turing: dove la testa di nastro è, ciò che lo stato attuale è, quali simboli sono scritti sul nastro, e quali transizioni sono validi in ogni posizione. Perché la NTM si ferma in tempo polinomiale, lo spazio di configurazione è delimitato e possiamo fare una (grande) espressione polinomiale a rappresentarlo.