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?
Was ist die Komplexität dieses Problems? (Wurde es schon einmal untersucht?)
quelle
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?
Was ist die Komplexität dieses Problems? (Wurde es schon einmal untersucht?)
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 3 ∧ F 2 genau dann erfüllt werden kann, wenn φ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.
quelle