Variante von Critical SAT

8

Die Sprache Critical SAT ist definiert als die Menge der -Booleschen Formeln f, so dass f U N S A T, aber das Entfernen einer Klausel aus f es erfüllbar macht. Es ist bekannt, dass Critical SAT D P -vollständig ist. Frage ich mich um die folgende Variante: Bei einer gegebenen C N F Formel f , ist es der Fall , dass f in ist U N S A T und daß es existiert eine Klausel c , so dass f c C.N.F.ffU.N.S.EINT.fD.P.C.N.F.ffU.N.S.EINT.c (anstelle aller Klauseln gibt es eine Klausel). Ist diese Variante D P auch vollständig?fcS.EINT.D.P.

John
quelle

Antworten:

8

Es ist klar, dass Ihre Sprache in DP ist. Um zu zeigen, dass es DP-schwer ist, werden wir eine Reduzierung von SAT-UNSAT auf Ihre Sprache geben, die wir CRIT-UNSAT nennen können. Bei einem gegebenen Paar von CNFs , lassen Sie x , y frische Variablen, und sei h = ( f ¬ x ) ( g x ) ( g y ) ¬ x ( x ¬ y ) . Hier f (f,G)x,y

h=(f¬x)(Gx)(Gy)¬x(x¬y).
bedeutet, ¬ x zu allen Klauseln von f hinzuzufügen.f¬x¬xf

Angenommen, ist erfüllbar und g ist nicht erfüllbar. Da g nicht erfüllbar ist, ist h nicht erfüllbar. Da f erfüllbar ist, ist h ¬ x erfüllbar. Somit ist h in CRIT-SAT.fGGhfh¬xh

Nehmen wir umgekehrt an, dass in CRIT-SAT ist. Da h unbefriedigend ist, ist g unbefriedigend. Für einige Klauseln c ist h c erfüllbar. Wenn c f ¬ x ist, ist h c eindeutig immer noch unbefriedigend. In ähnlicher Weise ist, wenn c g x ist, h c aufgrund von g y immer noch unbefriedigend . Wenn c g y oder c =hhGchccf¬xhccGxhcGycGy dann ist h c aufgrund von g x immer noch unbefriedigend. Somit ist c = ¬ x , was bedeutet, dass h | x = 1 ist erfüllbar, dh f ist erfüllbar.c=x¬yhcGxc=¬xh|x=1f

Yuval Filmus
quelle
1
Können Sie nicht einfach die zweite Instanz von für neue Variablen erstellen, um Doppelarbeit zu vermeiden ? G
Joshua Grochow
1
Welche Fallanalyse?
Radu GRIGore
1
@RaduGRIGore Wir können versuchen , zum Beispiel. Wenn ( f , g ) eine Instanz von SAT-UNSAT ist, dann ist h unbefriedigend und wird erfüllbar, wenn wir ¬ x entfernen . In der anderen Richtung, wenn h unbefriedigend ist, dann gh=(f¬x)(Gx)(Gy)¬x(x¬y)(f,G)h¬xhGist unbefriedigend. Wir müssen überprüfen, ob es jetzt eine Möglichkeit gibt, zu "betrügen" - um es durch Entfernen von zum Beispiel erfüllbar zu machen . In der Tat wird dies nicht helfen. Aber wir mussten noch einen Fall prüfen. x¬y
Yuval Filmus
3
Ich dachte , was Joshua sagte ist , wobei g 'h=(f¬x)(Gx)(G'x)¬xG' sieht aus wie , aber mit grundiert Variablen. G
Radu GRIGore
1
@ RaduGRIGore Richtig, das wäre ein einfacher Beweis.
Yuval Filmus