Der DOUBLE-SAT-Nachweis ist NP-vollständig

13

Das bekannte SAT-Problem wird hier als Referenz definiert .

Das DOUBLE-SAT-Problem ist definiert als

DOUBLE-SAT={ϕϕ has at least two satisfying assignments}

Wie beweisen wir, dass es NP-vollständig ist?

Es wird mehr als ein Weg geschätzt, dies zu beweisen.

pnp
quelle

Antworten:

25

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 .NPϕ(x1,,xn)ϕ

Um zu zeigen, dass Double-SAT -komplett ist, geben wir eine Reduktion von SAT auf Double-SAT wie folgt:NP

Bei Eingabe von :ϕ(x1,,xn)

  1. Führe eine neue Variable .y
  2. Ausgangsformel .ϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯)

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ϕ(x1,,xn)ϕϕ(x1,,xn,y)yy¯ oder y = 0 zu der neuen Variablen y , also ϕ ( xy=1y=0yϕ , ..., x n , y ) Doppel-SAT.x1xny

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ϕ(x1,,xn)SATϕ(x1,,xn,y)=ϕ(x1,,xn)(yy¯) .ϕ(x1,,xn,y)Double-SAT

Daher ist , und Double-SAT ist somit N P -komplett.SATpDouble-SATNP

pnp
quelle
Das ist schöner als mein Vorschlag.
Raphael
10

Sie wissen, dass NP-vollständig ist. Können Sie eine Reduzierung von S A T auf D O U finden?SATSAT? 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

Für jede Formel hat die Formel φ f ( φ ) mindestens die doppelte Anzahl erfüllender Bewertungen wie φφφf(φ)φ , wobei ein Homomorphismus ist, der alle Variablen in neue Namen umbenennt.f

Raphael
quelle