Wie beweisen Sie, dass SAT NP-Vervollständigung ist?

Question

Wie es ist, wie beweisen Sie, dass SAT NP-Vervollständigung ist?

Ich weiß, was es mit NP-Complete bedeutet, daher brauche ich keine Erklärung dazu.

Ich möchte wissen, woher Sie wissen, dass ein Problem wie SAT NP-Complete ist, ohne auf andere Probleme wie Hamiltonsche Probleme oder was auch immer zu reduzieren.

Answer 1

Ich glaube 21 NP-Complete-Probleme.

Wikipedia hat eine Beschreibung wie man zeigt, dass eine Erfüllbarkeit von NP-Vervollständigung ist, ein Ergebnis, das als das bekannt ist Cook-Levin-Theorem. Die Idee dieses Beweises ist zu zeigen, dass jede nicht -deterministische Turing -Maschine von Polynomzeit als boolescher Expression mit Polynomgröße modelliert werden kann. Der boolesche Ausdruck hat Begriffe, um den gültigen Konfigurationsraum der Turing -Maschine darzustellen: Wo der Bandkopf ist, was der aktuelle Zustand ist, welche Symbole auf dem Band geschrieben sind und welche Übergänge an jeder Position gültig sind. Da der NTM in der Polynomzeit eingestellt wird, ist der Konfigurationsraum begrenzt und wir können einen (großen) Polynomausdruck ausführen, um ihn darzustellen.