Wie beweisen Sie, dass SAT NP-vollständig ist?
Ich weiß, was es mit NP-vollständig bedeutet, daher brauche ich keine Erklärung dafür.
Was ich wissen möchte, ist, woher wissen Sie, dass ein Problem wie SAT NP-vollständig ist, ohne auf andere Probleme wie das Hamilton-Problem oder was auch immer zurückzugreifen.
complexity-theory
satisfiability
user2346
quelle
quelle
Antworten:
Ich glaube, 3-SAT wurde ursprünglich von der allgemeineren ZUFRIEDENHEIT in Karps Artikel reduziert, in der 21 NP-vollständige Probleme beschrieben wurden .
Wikipedia enthält eine Beschreibung, wie gezeigt werden kann, dass die ZUFRIEDENHEIT NP-vollständig ist, ein Ergebnis, das als Cook-Levin-Theorem bekannt ist . Die Idee dieses Beweises ist es zu zeigen, dass jede nichtdeterministische Turing-Maschine mit Polynomzeit als boolescher Ausdruck mit Polynomgröße modelliert werden kann. Der boolesche Ausdruck enthält Begriffe, die den gültigen Konfigurationsraum der Turing-Maschine darstellen: Wo sich der Bandkopf befindet, wie der aktuelle Status ist, welche Symbole auf das Band geschrieben sind und welche Übergänge an jeder Position gültig sind. Da der NTM in der Polynomzeit anhält, ist der Konfigurationsraum begrenzt und wir können einen (großen) Polynomausdruck erstellen, um ihn darzustellen.
quelle