Komplexität des SAT-Problems?

8

Definieren Sie das SAT-Problem: Gegeben sei , eine erfüllbare 3-CNF-Formel, und , eine 2-CNF-Formel ( und sind für dieselben Variablen definiert). Ist erfüllbar?(3,2)sF3F2F3F2F3F2

Was ist die Komplexität dieses Problems? (Wurde es schon einmal untersucht?)

Xavier Labouze
quelle

Antworten:

13

Dieses Problem ist NP-vollständig.

Sei eine beliebige CNF-Formel (eine Instanz von SAT). Betrachten Sie , wobei eine neue Variable ist. Offensichtlich ist diese Formel erfüllt (Sie können einfach auf true setzen). Konvertieren Sie nun mit einer beliebigen Standardmethode in 3-CNF und lassen Sie das Ergebnis bezeichnen. Beachten Sie, dass eine erfüllbare 3-CNF-Formel ist, sodass wir F 3 = ψ lassen können . Nun sei F 2 = ¬ y . Beachten Sie, dass F 3F 2 genau dann erfüllt werden kann, wenn φφφyyyφyψψF3=ψF2=¬yF3F2φist. Daher ist die SAT Problem ist mindestens so hart wie TV. Auch ist es eindeutig nicht schwerer als SAT. Daher ist es genauso schwierig wie SAT.(3,2)s

DW
quelle
Tks @DW, ziemlich überzeugend.
Xavier Labouze
Sie sollten nur von 3SAT statt von SAT reduzieren.
Tyson Williams
5
φφy
Ah ja. Guter Punkt.
Tyson Williams
2

F3F3F2

Xavier Labouze
quelle