Das bekannte SAT-Problem wird hier als Referenz definiert .
Das DOUBLE-SAT-Problem ist definiert als
Wie beweisen wir, dass es NP-vollständig ist?
Es wird mehr als ein Weg geschätzt, dies zu beweisen.
Das bekannte SAT-Problem wird hier als Referenz definiert .
Das DOUBLE-SAT-Problem ist definiert als
Wie beweisen wir, dass es NP-vollständig ist?
Es wird mehr als ein Weg geschätzt, dies zu beweisen.
Hier ist eine Lösung:
Zweifellos gehört Double-SAT zu , da ein NTM Double-SAT wie folgt entscheiden kann: Errate auf einer Booleschen Eingangsformel ϕ ( x 1 , … , x n ) nicht deterministisch 2 Zuweisungen und überprüfe, ob beide ϕ erfüllen .
Um zu zeigen, dass Double-SAT -komplett ist, geben wir eine Reduktion von SAT auf Double-SAT wie folgt:
Bei Eingabe von :
Wenn zu SAT gehört, hat ϕ mindestens 1 erfüllende Zuordnung, und daher hat ϕ ′ ( x 1 , … , x n , y ) mindestens 2 erfüllende Zuordnungen, wie wir die erfüllen können neue Klausel ( y ∨ ˉ y ) durch Zuweisen von entweder oder y = 0 zu der neuen Variablen y , also ϕ ′ ( x , ..., x n , y ) ∈ Doppel-SAT.
Wenn andererseits , dann ist eindeutig ϕ ′ ( x 1 , ... , x n , y ) = ϕ ( x 1 , ... , x n ) ∧ ( y ∨ ˉ y ) hat auch keine befriedigende Zuordnung, also ϕ ′ ( x 1 , … , x .
Daher ist , und Double-SAT ist somit N P -komplett.
Sie wissen, dass NP-vollständig ist. Können Sie eine Reduzierung von S A T auf D O U finden?SAT SAT ? Das heißt, können Sie eine erfüllbare Formel so manipulieren, dass das Ergebnis mindestens zwei erfüllende Zuweisungen hat? Beachten Sie, dass die gleiche Manipulation nicht zu befriedigenden Formeln führen kann.DOUBLE-SAT
quelle