Universal-Quantifizierer in QBFS

Question

Ich habe die Reduzierungen von / aus der TQBF-Sprache gesucht und gelungen, auf etwas stecken zu lassen, das fast sicher nicht wahr ist (oder wenn es wahr ist, fehlt mir eine signifikante, damit verbundene Rechenkosten) mit Respekt, um TQBF-Instanzen zu vereinfachen.

Lassen Sie uns der Einfachheit halber die Aufmerksamkeit auf TQBF-Instanzen in Prenex-Normalform und CNF ohne freie Variablen einschränken. Meine Hypothese (die ich stark vermute, ist falsch, ist jedoch nicht in der Lage, ein Gegenbeispiel nicht zu finden) ist, dass ein solcher TQBF, wenn und nur, wenn der TQBF, der sich aus dem Entfernen von allgemein quantifizierten Variablen aus dem Satz ergibt, erfüllt ist. Nehmen Sie zum Beispiel die folgende Instanz:

$ \ existiert A \ FORALL B \ existiert C \ FORALL D $ $ \ psi (A, B, C , d) $

$ \ psi (a, b, c, d)= (\ neg a \ vee b \ vee c) \ wedge (\ neg b \ vee \ neg c \ vee d) \ wedge (a \ vee c \ vee \ neg d) $

Zunächst ging ich daran, dass diese Instanz nicht erfüllt ist (leicht überprüfbar von Hand). Wenn wir die oben beschriebene Methode anwenden, erhalten wir den folgenden "Kern":

$ \ existiert A \ existiert C $ $ \ phi (a, c) $ , < / p>

$ \ phi (a, c)= (\ neg a \ vee c) \ wedge (\ neg c) \ wedge (a \ vee c) $

das ist eindeutig nicht erfüllt. Wenn wir anstelle dieses Beispiels folgen, sehen wir uns das an:

$ \ existiert A \ FORALL B \ existiert C \ FORALL D $ $ \ psi (A, B, C , d) $

$ \ psi (a, b, c, d)= (\ neg a \ vee b \ vee \ neg c) \ wedge (\ neg b \ vee c \ vee d) \ wedge (a \ vee c \ vee \ neg d) $

was eindeutig befriedigt ist (set c auf true, a to false) und der einen "Kern" von

hat

$ \ existiert A \ existiert C $ $ \ phi (a, c) $ , < / p>

$ \ phi (a, c)= (\ neg a \ vee \ neg c) \ wedge (c) \ wedge (a \ vee c) $

das ist auch mit den gleichen variablen Einstellungen erfüllt.

Wenn dieses Verfahren immer funktioniert, scheint dies zu deuten, dass eine Reduktion von TQBF ist, um in der Anzahl der universellen Quantifizierer und der Anzahl der Ereignisse der universell quantifizierten Variablen in der Formel in der Formel zu saß, die zeigt, dass TQBF angezeigt wird NP-COMPRETE (Es ist bereits bekannt als PSPACE-COMPRETE und somit NP-HARD, also, wenn es sich in NP handelt, ist es np-komplett) und darüber hinaus das NP= PSPACE. Ich wäre völlig fun, wenn dies der Fall ist, aber ich konnte keine Gegenexamplung (oder eine fehlende Rechenkosten in der Reduktion, die es nicht auf Polynomzeit macht, nicht finden. Was vermisse ich?

Answer 1

Ihre Intuition war richtig. Es funktioniert nicht. Hier ist ein Gegenbeispiel.

Betrachten Sie, $ \ FORALL A \ existiert B \ VARPHI (A, B) $ wobei $ \ varphi (A, b)= (a \ lor \ neg b) \ land (\ neg a \ lor b) $ . Diese Anweisung bewertet auf true.

Wenn wir jedoch $ a $ nach Ihrem Vorgang entfernen, erhalten wir $ \ existiert B \ PSI (B) $ wo $ \ psi (b)= ((\ neg b) \ land (b)) $ ; und diese Aussage bewertet falsch.

Eine Möglichkeit, zu verstehen, warum Ihre Methode nicht funktioniert, ist, dass $ \ FORALL A \ Exists B \ Varphi (A, B) $ nicht gleichwertig ist $ \ existiert B \ nachall a \ varphi (a, b) $ . Möglicherweise funktioniert Ihre Methode möglicherweise, wenn der gesamte $ \ fürall $ innen ist, dh für einen Satz des Formulars $ \ existieren \ CDOTs \ existieren \ vorläufig \ CDs \ Forall $ , aber nicht für jedes andere Muster von $ \ gibt es $ und $ \ vorläufig $ .