True quantifizierte boolesche Formel

Im Computerkomplexitätstheorie, die Sprache Tqbf ist ein formelle Sprache bestehend aus dem echte quantifizierte Boolesche Formeln. A (vollständig) quantifizierte boolesche Formel ist eine Formel in quantifiziert Aussagelogik wo jede Variable quantifiziert wird (oder gebunden) mit entweder existenziell oder Universal- Quantifizierer zu Beginn des Satzes. Eine solche Formel entspricht entweder wahr oder falsch (da es keine gibt freie Variablen). Wenn eine solche Formel auf wahr bewertet wird, befindet sich diese Formel in der Sprache TQBF. Es ist auch als bekannt als als QSAT (Quantifiziert Sa).

Überblick

In der rechnerischen Komplexitätstheorie die Quantifiziertes Problem der Booleschen Formel (QBF) ist eine Verallgemeinerung der Boolesche Zufriedenheitsproblem in welch beides existenzielle Quantifizierer und Universelle Quantifizierer kann auf jede Variable angewendet werden. Anders ausgedrückt, es wird gefragt, ob eine quantifizierte Sententialform über eine Reihe von booleschen Variablen wahr oder falsch ist. Beispielsweise ist das Folgende eine Instanz von QBF:

{\ displaystyle \ forall x \ \ existiert y \ \ exists z \ ((x \ lor z) \ land y)}

QBF ist der Kanonisch Vollständiges Problem zum PSPACE, die Klasse der Probleme, die durch eine deterministische oder nicht deterministische Probleme lösbar sind Turing Maschine im Polynomraum und unbegrenzte Zeit.^[1] Angesichts der Formel in Form eines Zusammenfassung SyntaxbaumDas Problem kann leicht durch eine Reihe von gegenseitig rekursiven Verfahren gelöst werden, die die Formel bewerten. Ein solcher Algorithmus nutzt Raum proportional zur Höhe des Baumes, der im schlimmsten Fall linear ist, aber zeitlich exponentiell in der Anzahl der Quantifizierer verwendet.

Unter der Vorraussetzung, dass Ma ⊊ PSPACE, was allgemein angenommen wird, kann qBF nicht gelöst werden, und eine bestimmte Lösung kann auch nicht in deterministischem oder sogar überprüft werden probabilistisch Polynomzeit (tatsächlich gibt es im Gegensatz zum Befriedigungsproblem keinen bekannten Weg, eine Lösung kurz und bündig anzugeben). Es kann mit einem gelöst werden Wechsel Turing Machine in linearer Zeit seitdem AP = PSPACE, wobei AP die Klasse von Problemen ist, die wechselnde Maschinen in der Polynomzeit lösen können.^[2]

Wenn das wegweisende Ergebnis IP = PSPACE wurde gezeigt (siehe Interaktives Proof -System), Es wurde durchgeführt, indem ein interaktives Proof -System aufwies, das QBF durch Lösen einer bestimmten Arithmetisierung des Problems lösen konnte.^[3]

QBF -Formeln haben eine Reihe nützlicher kanonischer Formen. Zum Beispiel kann gezeigt werden, dass es a gibt Polynomzeit viele eins Reduktion Das wird alle Quantifizierer in die Vorderseite der Formel bewegen und sie zwischen universellen und existenziellen Quantifizierern abwechseln. Es gibt eine weitere Reduzierung, die sich im IP = PSPACE -Beweis als nützlich erwiesen hat, bei dem nicht mehr als ein universeller Quantifizierer zwischen den Verwendung der einzelnen Variablen und der Quantifiziererbindung dieser Variablen platziert wird. Dies war entscheidend, um die Anzahl der Produkte in bestimmten Unterexpressionen der Arithmetisierung zu begrenzen.

Prenex normale Form

Es kann angenommen werden, dass eine vollständig quantifizierte Boolesche Formel eine sehr spezifische Form hat, genannt Prenex normale Form. Es hat zwei grundlegende Teile: einen Teil, der nur Quantifizierer und einen Teil mit einer nicht quantifizierten booleschen Formel enthält, die normalerweise als als bezeichnet ist ${\ displayStyle \ displayStyle \ phi}$ . Wenn es gibt ${\ displayStyle \ displayStyle n}$ Boolesche Variablen, die gesamte Formel kann geschrieben werden

oder , \ dots, x_ {n})}

wo jede Variable in die fällt Umfang von einem Quantifizierer. Durch die Einführung von Dummy -Variablen kann jede Formel in Prenex -Normalform in einen Satz umgewandelt werden, bei dem existenzielle und universelle Quantifizierer abwechseln. Verwenden der Dummy -Variablen ${\ displaystyle \ displayStyle y_ {1}}$ Anwesend

oder x_ {2} \ phi (x_ {1}, x_ {2})}

Der zweite Satz hat das gleiche Wahrheitswert folgt aber der eingeschränkten Syntax. Die Annahme, dass vollständig quantifizierte Boolesche Formeln in Prenex -Normalform befinden, ist ein häufiges Merkmal von Proofs.

QBF -Löser

Naiv

Es gibt einen einfachen rekursiven Algorithmus, um festzustellen, ob sich ein QBF in TQBF befindet (d. H. IS wahr). Angesichts einiger QBF

oder .}

Wenn die Formel keine Quantifizierer enthält, können wir einfach die Formel zurückgeben. Andernfalls nehmen wir den ersten Quantifizierer ab und überprüfen beide möglichen Werte für die erste Variable:

oder

oder

Wenn ${\ displayStyle q_ {1} = \ existiert}$ , dann kehren Sie zurück ${\ displayStyle a \ lor b}$ . Wenn ${\ displayStyle q_ {1} = \ forall}$ , dann kehren Sie zurück $A\land B$ .^[4]

Wie schnell läuft dieser Algorithmus? Für jeden Quantifizierer im anfänglichen QBF führt der Algorithmus zwei rekursive Aufrufe nur auf ein linear kleineres Teilproblem. Dies gibt dem Algorithmus eine exponentielle Laufzeit O (2ⁿ).

Wie viel Platz nutzt dieser Algorithmus? Innerhalb jeder Aufruf des Algorithmus muss die Zwischenergebnisse von Computing A und B speichern. Jeder rekursive Aufruf nimmt einen Quantifizierer aus, sodass die Gesamttiefe in der Anzahl der Quantifizierer linear ist. Formeln, bei denen keine Quantifizierer fehlen, können in der Anzahl der Variablen in Raumlogarithmikum bewertet werden. Der anfängliche QBF wurde vollständig quantifiziert, so dass es mindestens so viele Quantifizierer wie Variablen gibt. Somit verwendet dieser Algorithmus O(n + log n) = O(n) Platz. Dies macht die TQBF -Sprache Teil der PSPACE Komplexitätsklasse.

Der letzte Stand der Technik

Trotz der PSPACE-Vervollständigung von QBF wurden viele Löser entwickelt, um diese Instanzen zu lösen. (Dies ist analog zur Situation mit Sa, die einzelne existenzielle Quantifiziererversion; obwohl es ist NP-CompleteEs ist immer noch möglich, viele SAT -Instanzen heuristisch zu lösen.)^[5]^[6] Der Fall, in dem es nur 2 Quantifizierer gibt, die als 2QBF bezeichnet werden, hat besondere Aufmerksamkeit erhalten.^[7]^{[Wieselwörter]}

Der QBF-Solver-Wettbewerb QBFeval läuft seit 2004 mehr oder weniger ohne mehr oder ohne mehr.^[5]^[6] Löser müssen Instanzen im QDIMACS -Format und entweder im QCIR- oder im Qaiger -Formaten lesen.^[8] Hochleistungsfähige QBF-Solvers verwenden im Allgemeinen QDPLL (eine Verallgemeinerung von Dpll) oder Cegar.^[5]^[6]^[7] Die Erforschung der QBF -Lösung begann mit der Entwicklung von Backtracking -DPLL für QBF im Jahr 1998, gefolgt von der Einführung des Lernens der Klausel und der variablen Eliminierung im Jahr 2002;^[9] Im Vergleich zur SAT -Lösung, die seit den 1960er Jahren entwickelt ist, ist QBF ab 2017 ein relativ junges Forschungsfeld.^[9]^{[Wieselwörter]}

Einige prominente QBF -Solvers sind:

Kadett, der quantifizierte boolesche Formeln löst, die auf eine Quantifiziererwechsel beschränkt sind (mit der Fähigkeit zu berechnen Skolem Funktionen), bezogen auf Inkrementelle Bestimmung^{[Klarstellung erforderlich]} und mit der Fähigkeit, seine Antworten zu beweisen.^[10]
CAQE - Ein Cegar -basierter Solver für quantifizierte boolesche Formeln; Gewinner der jüngsten Ausgaben von QBfeval.^[11]
DepQBF - Ein suchbasierter Löser für quantifizierte boolesche Formeln^[12]
SKIZZO - Der erste Solver, der jemals symbolische Skolemisierung verwendet, erfreute Zertifikate extrahiert, eine Hybrid -Inferenz -Engine verwendet, abstrakte Verzweigungen implementieren, mit begrenzten Quantifizierern umgehen und gültige Aufgaben und Gewinner von QBFeval 2005, 2006 und 2007 aufzählen.^[13]

Anwendungen

QBF -Löser können auf die Planung (in künstlicher Intelligenz), einschließlich einer sicheren Planung, angewendet werden. Letzteres ist entscheidend für Anwendungen von Robotik.^[14] QBF -Löser können auch auf angewendet werden Begrenzte Modellprüfung da sie eine kürzere Codierung bieten, als für einen Sat-basierten Löser benötigt wird.^[14]

Die Bewertung eines QBF kann als a gesehen werden Zwei-Spieler-Spiel Zwischen einem Spieler, der existententiell quantifizierte Variablen kontrolliert, und einem Spieler, der universell quantifizierte Variablen kontrolliert. Dies macht QBFs für die Codierung geeignet reaktive Synthese Probleme.^[14] In ähnlicher Weise können QBF -Solvers verwendet werden Spieltheorie. Zum Beispiel können QBF -Solvers verwendet werden, um zu finden Gewinnstrategien für Spiele von Erdkunde, was dann automatisch interaktiv gespielt werden kann.^[15]

QBF -Löser können für verwendet werden Formale Äquivalenzprüfungund kann auch verwendet werden, um die Booleschen Funktionen zu synthetisieren.^[14]

Andere Arten von Problemen, die als QBFS codiert werden können, sind:

Erkennen, ob eine Klausel in einer unbefriedigbaren Formel in Konjunktive normale Form gehört zu einer minimal unbefriedigenden Teilmenge^[9]^[16] und ob eine Klausel in einer zufriedenbaren Formel zu einer maximal zufriedenbaren Teilmenge gehört^[16]
Kodierungen der konformanten Planung^[9]^{[Klarstellung erforderlich]}
ASP-bezogene Probleme^[9]^{[Klarstellung erforderlich]}
Abstrakte Argumentation^[9]^{[Klarstellung erforderlich]}
Lineare zeitliche Logik Modellprüfung^[9]^{[Klarstellung erforderlich]}
Nichtdeterministisches endliches Automaten Spracheinschluss^[9]^{[Klarstellung erforderlich]}
Synthese und Zuverlässigkeit verteilter Systeme^[9]^{[Klarstellung erforderlich]}

Erweiterungen

In QBfeval 2020 wurde ein "DQBF -Track" eingeführt, in dem Instanzen haben durften Henkin -Quantifizierer (ausgedrückt im DQDIMACS -Format).^[8]

PSPACE-Completness

Die TQBF -Sprache dient in Komplexitätstheorie als Kanonisch PSPACE-Complete Problem. PSPACE-Complete zu sein bedeutet, dass eine Sprache im PSPACE ist und dass die Sprache auch ist PSPACE-HARD. Der obige Algorithmus zeigt, dass sich TQBF in PSPACE befindet. Das Zeigen, dass TQBF PSPACE-HARD ist, muss zeigen, dass jede Sprache in der Komplexitätsklasse PSPACE in der Polynomzeit auf TQBF reduziert werden kann. D.h.

oder

Dies bedeutet, dass für eine PSPACE -Sprache L, ob eine Eingabe $x$ Is in l kann durch Überprüfen der Überprüfung, ob überprüft werden, entschieden werden, ob ${\ displayStyle f (x)}$ ist in TQBF, für einige Funktionen $f$ Dies ist erforderlich, um in Polynomzeit zu laufen (relativ zur Länge des Eingangs). Symbolisch,

{\ displayStyle x \ in l \ iff f (x) \ in \ mathrm {tqbf}.}.}.

Das Beweisen, dass TQBF PSPACE-HART ist, erfordert die Spezifikation von $f$ .

Nehmen wir also an, dass L eine PSPACE -Sprache ist. Dies bedeutet, dass L von einem Polynomraum deterministisch entschieden werden kann Turing Maschine (DTM). Dies ist sehr wichtig für die Reduzierung von L zu TQBF, da die Konfigurationen einer solchen Turing -Maschine als boolesche Formeln dargestellt werden können, wobei Boolesche Variablen den Zustand der Maschine sowie den Inhalt jeder Zelle auf dem Turing -Maschinenband darstellen, mit der Position des Turing Machine Head in der Formel durch die Bestellung der Formel kodiert. Insbesondere wird unsere Reduzierung die Variablen verwenden ${\ displayStyle c_ {1}}$ und ${\ displayStyle c_ {2}}$ , die zwei mögliche Konfigurationen des DTM für L und eine natürliche Zahl t darstellen, um eine QBF zu konstruieren ${\ displaystyle \ phi _ {c_ {1}, c_ {2}, t}}$ Dies ist wahr, wenn und nur dann, wenn der DTM für L von der Konfiguration in codiert wird ${\ displayStyle c_ {1}}$ an die Konfiguration codiert in ${\ displayStyle c_ {2}}$ In nicht mehr als T -Schritten. Die Funktion $f$ Konstruiert dann aus dem DTM für L a QBF $oder$ , wo ${\ displayStyle c_ {start}}$ ist die Startkonfiguration des DTM, ${\ displayStyle c _ {\ text {Akzeptieren}}}$ ist die Akzeptanzkonfiguration des DTM, und T ist die maximale Anzahl von Schritten, die der DTM benötigt, um von einer Konfiguration zur anderen zu wechseln. Wir wissen das T = O(exp (n)), wobei n die Länge des Eingangs ist, da dies die Gesamtzahl der möglichen Konfigurationen des relevanten DTM begrenzt. Natürlich kann die DTM nicht mehr Schritte unternehmen, als mögliche Konfigurationen zu erreichen sind ${\ displayStyle c _ {\ mathrm {Akzeptieren}}}$ Es sei denn, es tritt in eine Schleife ein, in diesem Fall wird es niemals erreichen ${\ displayStyle c _ {\ mathrm {Akzeptieren}}}$ ohnehin.

In dieser Phase des Beweises haben wir bereits die Frage reduziert, ob eine Eingangsformel $w$ (natürlich codiert in ${\ displayStyle c _ {\ text {start}}}$ ) ist in L der Frage, ob der QBF $oder$ , d.h. ${\ displayStyle f (w)}$ , ist in TQBF. Der Rest dieses Beweises beweist das $f$ kann in Polynomzeit berechnet werden.

Zum ${\ displayStyle t = 1}$ , Berechnung von ${\ displaystyle \ phi _ {c_ {1}, c_ {2}, t}}$ ist unkompliziert - entweder eine der Konfigurationen ändert sich in einem Schritt an der anderen oder nicht. Da die Turing -Maschine, die unsere Formel darstellt, deterministisch ist, zeigt dies kein Problem.

Zum ${\ displayStyle t> 1}$ , Berechnung von ${\ displaystyle \ phi _ {c_ {1}, c_ {2}, t}}$ beinhaltet eine rekursive Bewertung, die nach einem sogenannten "Mittelpunkt" sucht ${\ displayStyle m_ {1}}$ . In diesem Fall schreiben wir die Formel wie folgt um:

oder Keil \ phi _ {m_ {1}, c_ {2}, \ lceil t/2 \ rceil}).}

Dies wandelt die Frage, ob ${\ displayStyle c_ {1}}$ kann erreichen ${\ displayStyle c_ {2}}$ In t Schritte zur Frage, ob ${\ displayStyle c_ {1}}$ erreicht einen Mittelpunkt ${\ displayStyle m_ {1}}$ in ${\ displayStyle t/2}$ Schritte, die selbst erreicht ${\ displayStyle c_ {2}}$ in ${\ displayStyle t/2}$ Schritte. Die Antwort auf die letztere Frage gibt natürlich die Antwort auf die erstere.

Jetzt wird t nur durch T begrenzt, was exponentiell (und damit nicht Polynom) in der Länge des Eingangs ist. Zusätzlich verdoppelt jede rekursive Schicht praktisch die Länge der Formel. (Die Variable ${\ displayStyle m_ {1}}$ ist nur ein Mittelpunkt - für größere T gibt es sozusagen mehr Stopps auf dem Weg.) Die Zeit, die für die rekursive Bewertung erforderlich ist ${\ displaystyle \ phi _ {c_ {1}, c_ {2}, t}}$ Auf diese Weise könnte auch exponentiell sein, einfach weil die Formel exponentiell groß werden könnte. Dieses Problem wird durch universelle Quantifizierung mit Variablen gelöst ${\ displayStyle c_ {3}}$ und ${\ displayStyle c_ {4}}$ über die Konfigurationspaare (z. B.,, ${\ displayStyle \ {(c_ {1}, m_ {1}), (m_ {1}, c_ {2}) \}}$ ), was verhindert, dass die Länge der Formel aufgrund rekursiver Schichten expandiert. Dies ergibt die folgende Interpretation von ${\ displaystyle \ phi _ {c_ {1}, c_ {2}, t}}$ :

oder {1}), (m_ {1}, c_ {2}) \} (\ phi _ {c_ {3}, c_ {4}, \ lceil t/2 \ rceil}).}

Diese Version der Formel kann in der Polynomzeit tatsächlich berechnet werden, da eine Instanz davon in der Polynomzeit berechnet werden kann. Das universell quantifizierte geordnete Paar sagt uns ledig ${\ displayStyle (c_ {3}, c_ {4})}$ ist gemacht, $oder$ .

Daher, $oder$ so ist TQBF PSPACE-HARD. Zusammen mit dem obigen Ergebnis, dass TQBF in PSPACE ist, wird der Beweis vervollständigt, dass TQBF eine PSPACE-Vervollständigung ist.

(Dieser Beweis folgt Sipser 2006 S. 310–313 in allen wichtigen Wesentlichen. Papadimitriou 1994 enthält auch einen Beweis.)

Miscellany

Ein wichtiges Teilproblem in TQBF ist das Boolesche Zufriedenheitsproblem. In diesem Problem möchten Sie wissen, ob eine bestimmte boolesche Formel ${\ displayStyle \ phi}$ Kann mit einer gewissen Zuordnung von Variablen wahr gemacht werden. Dies entspricht dem TQBF nur mit existenziellen Quantifizierern: $oder$ Dies ist auch ein Beispiel für das größere Ergebnis NP ⊆ PSPACE, das direkt aus der Beobachtung folgt, dass eine Polynomzeitprüfer für einen von einem NTM akzeptierten Sprache (von einem NTM akzeptiert (Nichtdeterministische Turing-Maschine) Erfordert Polynomraum, um den Beweis zu speichern.
Jede Klasse in der Polynomhierarchie (PH) hat TQBF als hartes Problem. Mit anderen Worten, für die Klasse, die alle Sprachen l umfasst, für die es einen Poly-Zeit-TM V gibt, einen Verifier, so dass für alle Eingaben x und einige Konstante i, $oder {i}) \ = \ 1}$ die eine spezifische QBF -Formulierung hat, die als angegeben wird ${\ displayStyle \ existiert \ phi}$ so dass $oder {x_ {1}}}, {\ vec {x_ {2}}}, \ dots, {\ vec {x_ {i}}) \ = \ 1}$ bei dem die ${\ displaystyle {\ vec {x_ {i}}}}$ 'S sind Vektoren von booleschen Variablen.
Es ist wichtig zu beachten, dass die Sprache zwar als TQBF als die Sammlung echtem quantifizierten booleschen Formeln definiert ist, die Abkürzung TQBF häufig verwendet wird (sogar in diesem Artikel), um für eine völlig quantifizierte boolesche Formel zu stehen, die häufig einfach als QBF bezeichnet wird (quantifizierter boolean Formel, als "vollständig" oder "völlig" quantifiziert). Es ist wichtig, kontextuell zwischen den beiden Verwendungen der Abkürzung TQBF beim Lesen der Literatur zu unterscheiden.
Ein TQBF kann als ein Spiel zwischen zwei Spielern mit abwechselnden Bewegungen angesehen werden. Existenziell quantifizierte Variablen entsprechen der Vorstellung, dass einem Spieler in einer Runde ein Schritt zur Verfügung steht. Allgemein quantifizierte Variablen bedeuten, dass das Ergebnis des Spiels nicht davon abhängt, welche Bewegung ein Spieler in dieser Runde macht. Auch ein TQBF, dessen erster Quantifizierer existentiell ist, entspricht a Formelspiel in dem der erste Spieler eine Gewinnstrategie hat.
Eine TQBF, für die sich die quantifizierte Formel befindet 2-CNF Kann gelöst werden lineare Zeit, durch einen Algorithmus mit Starke Konnektivitätsanalyse von seinem Implikationsgrafik. Das 2-Satsfabilität Das Problem ist ein Sonderfall von TQBF für diese Formeln, bei denen jeder Quantifizierer existentiell ist.^[17]^[18]
Es gibt eine systematische Behandlung von eingeschränkten Versionen quantifizierter boolescher Formeln (die Schäfer-Klassifikationen verleihen) in einem Expository-Papier von Hubie Chen bereitgestellt.^[19]
Planar TQBF, Verallgemeinerung Planar saß, wurde von D. lichtenstein nachgewiesen.^[20]

Notizen und Referenzen

^ M. Garey & D. Johnson (1979). Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung. W. H. Freeman, San Francisco, Kalifornien. ISBN 0-7167-1045-5.
^ A. Chandra, D. Kozen und L. Stockmeyer (1981). "Wechsel". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
^ Adi Shamir (1992). "IP = PSPACE". Journal of the ACM. 39 (4): 869–877. doi:10.1145/146585.146609. S2CID 315182.
^ Arora, Sanjeev; Barak, Boaz (2009), "Raumkomplexität", Rechenkomplexität, Cambridge: Cambridge University Press, S. 78–94, doi:10.1017/CBO9780511804090.007, ISBN 978-0-511-80409-0, abgerufen 2021-05-26
^ ^a ^b ^c "Qbfeval Homepage". www.qbflib.org. Abgerufen 2021-02-13.
^ ^a ^b ^c "QBF Solvers | Beyond NP". Beyondnp.org. Abgerufen 2021-02-13.
^ ^a ^b Balabanov, Valeriy; Roland Jiang, Jie-Hong; Scholl, Christoph; Mishchenko, Alan; K. Brayton, Robert (2016). "2QBF: Herausforderungen und Lösungen" (PDF). Internationale Konferenz über Theorie und Anwendungen von Erfüllbarkeitstests: 453–459. Archiviert (PDF) vom Original am 13. Februar 2021 - über Springerlink.
^ ^a ^b "Qbfeval'20". www.qbflib.org. Abgerufen 2021-05-29.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Lonsing, Florian (Dezember 2017). "Eine Einführung in die QBF -Lösung" (PDF). www.florianlonsing.com. Abgerufen 29. Mai 2021.{{}}: CS1 Wartung: URL-Status (Link)
^ Rabe, Markus N. (2021-04-15), Markusrabe/Kadett, abgerufen 2021-05-06
^ Tentrup, Leander (2021-05-06), Ltentrup/Caqe, abgerufen 2021-05-06
^ "Depqbf Solver". lonsing.github.io. Abgerufen 2021-05-06.
^ "Skizzo - ein QBF -Solver". www.skizzo.site. Abgerufen 2021-05-06.
^ ^a ^b ^c ^d Shukla, Ankit; Biere, Armin; Seidl, Martina; Pulina, Luca (2019). Eine Umfrage zu Anwendungen quantifizierter boolescher Formeln (PDF). 2019 IEEE 31. Internationale Konferenz über Tools für künstliche Intelligenz. S. 78–84. doi:10.1109/ictai.2019.00020. Abgerufen 29. Mai 2021.
^ Shen, Zhihe. Verwenden von QBF -Solvers, um Spiele und Rätsel zu lösen (PDF) (These). Boston College.
^ ^a ^b Janota, Mikoláš; Marques-Silva, Joao (2011). Bei der Entscheidung der MUS -Mitgliedschaft bei QBF. Prinzipien und Praxis der Einschränkungsprogrammierung - CP 2011. Vol. 6876. S. 414–428. doi:10.1007/978-3-642-23786-7_32. ISBN 978-3-642-23786-7.
^ Krom, Melven R. (1967). "Das Entscheidungsproblem für eine Klasse von Formeln erster Ordnung, in denen alle Unterlagen binär sind". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. 13 (1–2): 15–20. doi:10.1002/Malq.19670130104..
^ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979). "Ein linearer Zeitalgorithmus zum Testen der Wahrheit bestimmter quantifizierter boolescher Formeln" (PDF). Informationsverarbeitungsbriefe. 8 (3): 121–123. doi:10.1016/0020-0190 (79) 90002-4..
^ Chen, Hubie (Dezember 2009). "Ein Rendezvous von Logik, Komplexität und Algebra". ACM Computing -Umfragen. ACM. 42 (1): 1–32. Arxiv:CS/0611018. doi:10.1145/1592451.1592453. S2CID 11975818.
^ Lichtenstein, David (1982-05-01). "Planare Formeln und ihre Verwendung". Siam Journal über Computing. 11 (2): 329–343. doi:10.1137/0211025. ISSN 0097-5397.

Fortnow & Homer (2003) bietet einen historischen Hintergrund für PSPACE und TQBF.
Zhang (2003) bietet einen historischen Hintergrund von Booleschen Formeln.
Arora, Sanjeev. (2001). Cos 522: Computerkomplexität. Vorlesungsnotizen, Princeton University. Abgerufen am 10. Oktober 2005.
Fortnow, Lance & Steve Homer. (2003, Juni). Eine kurze Geschichte der rechnerischen Komplexität. Die Spalte der Computerkomplexität,, 80. Abgerufen am 9. Oktober 2005.
Papadimitriou, C. H. (1994). Rechenkomplexität. Lesen: Addison-Wesley.
Sipser, Michael. (2006). Einführung in die Berechnungstheorie. Boston: Thomson -Kurs -Technologie.
Zhang, Lintao. (2003). Suche nach Wahrheit: Techniken zur Erfreulichkeit von Booleschen Formeln. Abgerufen am 10. Oktober 2005.

Siehe auch

Cook -Levin -Theorem, das zu sagen Sa ist NP-Complete
Verallgemeinerte Geographie

Externe Links

Die quantifizierte Boolesche Formelnbibliothek (QBflib)
Internationaler Workshop zu quantifizierten booleschen Formeln

[1] M. Garey & D. Johnson (1979). Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung. W. H. Freeman, San Francisco, Kalifornien. ISBN 0-7167-1045-5.

[2] A. Chandra, D. Kozen und L. Stockmeyer (1981). "Wechsel". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)

[3] Adi Shamir (1992). "IP = PSPACE". Journal of the ACM. 39 (4): 869–877. doi:10.1145/146585.146609. S2CID 315182.

[4] Arora, Sanjeev; Barak, Boaz (2009), "Raumkomplexität", Rechenkomplexität, Cambridge: Cambridge University Press, S. 78–94, doi:10.1017/CBO9780511804090.007, ISBN 978-0-511-80409-0, abgerufen 2021-05-26

[:0-5] "Qbfeval Homepage". www.qbflib.org. Abgerufen 2021-02-13.

[:1-6] "QBF Solvers | Beyond NP". Beyondnp.org. Abgerufen 2021-02-13.

[:2-7] Balabanov, Valeriy; Roland Jiang, Jie-Hong; Scholl, Christoph; Mishchenko, Alan; K. Brayton, Robert (2016). "2QBF: Herausforderungen und Lösungen" (PDF). Internationale Konferenz über Theorie und Anwendungen von Erfüllbarkeitstests: 453–459. Archiviert (PDF) vom Original am 13. Februar 2021 - über Springerlink.

[:3-8] "Qbfeval'20". www.qbflib.org. Abgerufen 2021-05-29.

[:4-9] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Lonsing, Florian (Dezember 2017). "Eine Einführung in die QBF -Lösung" (PDF). www.florianlonsing.com. Abgerufen 29. Mai 2021.{{}}: CS1 Wartung: URL-Status (Link)

[10] Rabe, Markus N. (2021-04-15), Markusrabe/Kadett, abgerufen 2021-05-06

[11] Tentrup, Leander (2021-05-06), Ltentrup/Caqe, abgerufen 2021-05-06

[12] "Depqbf Solver". lonsing.github.io. Abgerufen 2021-05-06.

[13] "Skizzo - ein QBF -Solver". www.skizzo.site. Abgerufen 2021-05-06.

[:5-14] Shukla, Ankit; Biere, Armin; Seidl, Martina; Pulina, Luca (2019). Eine Umfrage zu Anwendungen quantifizierter boolescher Formeln (PDF). 2019 IEEE 31. Internationale Konferenz über Tools für künstliche Intelligenz. S. 78–84. doi:10.1109/ictai.2019.00020. Abgerufen 29. Mai 2021.

[15] Shen, Zhihe. Verwenden von QBF -Solvers, um Spiele und Rätsel zu lösen (PDF) (These). Boston College.

[:6-16] Janota, Mikoláš; Marques-Silva, Joao (2011). Bei der Entscheidung der MUS -Mitgliedschaft bei QBF. Prinzipien und Praxis der Einschränkungsprogrammierung - CP 2011. Vol. 6876. S. 414–428. doi:10.1007/978-3-642-23786-7_32. ISBN 978-3-642-23786-7.

[17] Krom, Melven R. (1967). "Das Entscheidungsproblem für eine Klasse von Formeln erster Ordnung, in denen alle Unterlagen binär sind". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. 13 (1–2): 15–20. doi:10.1002/Malq.19670130104..

[18] Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979). "Ein linearer Zeitalgorithmus zum Testen der Wahrheit bestimmter quantifizierter boolescher Formeln" (PDF). Informationsverarbeitungsbriefe. 8 (3): 121–123. doi:10.1016/0020-0190 (79) 90002-4..

[19] Chen, Hubie (Dezember 2009). "Ein Rendezvous von Logik, Komplexität und Algebra". ACM Computing -Umfragen. ACM. 42 (1): 1–32. Arxiv:CS/0611018. doi:10.1145/1592451.1592453. S2CID 11975818.

[20] Lichtenstein, David (1982-05-01). "Planare Formeln und ihre Verwendung". Siam Journal über Computing. 11 (2): 329–343. doi:10.1137/0211025. ISSN 0097-5397.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]