Fórmula booleana cuantificada verdadera

En la teoría de la complejidad computacional , el lenguaje TQBF es un lenguaje formal que consiste en las fórmulas booleanas cuantificadas verdaderas . Una fórmula booleana (totalmente) cuantificada es una fórmula en lógica proposicional cuantificada (también conocida como lógica proposicional de segundo orden ) donde cada variable se cuantifica (o se limita ), utilizando cuantificadores existenciales o universales , al comienzo de la oración. Tal fórmula es equivalente a verdadero o falso (ya que no hay variables libres ). Si tal fórmula evalúa a verdadero, entonces esa fórmula está en el lenguaje TQBF. También se conoce como QSAT ( SAT cuantificado ).

Descripción general

En la teoría de la complejidad computacional, el problema de la fórmula booleana cuantificada ( QBF ) es una generalización del problema de satisfacibilidad booleana en el que se pueden aplicar tanto cuantificadores existenciales como cuantificadores universales a cada variable. Dicho de otro modo, pregunta si una forma oracional cuantificada sobre un conjunto de variables booleanas es verdadera o falsa. Por ejemplo, la siguiente es una instancia de QBF:

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

QBF es el problema completo canónico para PSPACE , la clase de problemas solucionables mediante una máquina de Turing determinista o no determinista en un espacio polinomial y tiempo ilimitado. ^[1] Dada la fórmula en forma de un árbol de sintaxis abstracta , el problema se puede resolver fácilmente mediante un conjunto de procedimientos recursivos mutuos que evalúan la fórmula. Un algoritmo de este tipo utiliza un espacio proporcional a la altura del árbol, que es lineal en el peor de los casos, pero utiliza un tiempo exponencial en el número de cuantificadores.

Siempre que MA ⊊ PSPACE, como se cree ampliamente, QBF no se puede resolver, ni se puede verificar una solución dada, ni en tiempo polinomial determinista ni en tiempo probabilístico (de hecho, a diferencia del problema de satisfacibilidad, no se conoce ninguna forma de especificar una solución de manera sucinta). Se puede resolver utilizando una máquina de Turing alternada en tiempo lineal, ya que AP = PSPACE, donde AP es la clase de problemas que las máquinas alternadas pueden resolver en tiempo polinomial. ^[2]

Cuando se mostró el resultado seminal IP = PSPACE (ver sistema de prueba interactivo ), se hizo exhibiendo un sistema de prueba interactivo que podía resolver QBF resolviendo una aritmetización particular del problema. ^[3]

Las fórmulas QBF tienen varias formas canónicas útiles. Por ejemplo, se puede demostrar que existe una reducción de muchos a uno en tiempo polinómico que moverá todos los cuantificadores al principio de la fórmula y hará que se alternen entre cuantificadores universales y existenciales. Existe otra reducción que resultó útil en la prueba IP = PSPACE, donde no se coloca más de un cuantificador universal entre el uso de cada variable y el cuantificador que vincula esa variable. Esto fue fundamental para limitar la cantidad de productos en ciertas subexpresiones de la aritmetización.

Forma normal de Prenex

Se puede suponer que una fórmula booleana completamente cuantificada tiene una forma muy específica, llamada forma normal prenex . Tiene dos partes básicas: una parte que contiene solo cuantificadores y una parte que contiene una fórmula booleana no cuantificada que generalmente se denota como . Si hay variables booleanas, la fórmula completa se puede escribir como ${\displaystyle \displaystyle \phi }$ ${\displaystyle \displaystyle n}$

${\displaystyle \displaystyle \exists x_{1}\forall x_{2}\exists x_{3}\cdots Q_{n}x_{n}\phi (x_{1},x_{2},x_{3},\dots ,x_{n})}$

donde cada variable cae dentro del alcance de algún cuantificador. Al introducir variables ficticias, cualquier fórmula en forma normal prenex se puede convertir en una oración donde se alternan cuantificadores existenciales y universales. Usando la variable ficticia , ${\displaystyle \displaystyle y_{1}}$

${\displaystyle \displaystyle \exists x_{1}\exists x_{2}\phi (x_{1},x_{2})\quad \mapsto \quad \exists x_{1}\forall y_{1}\exists x_{2}\phi (x_{1},x_{2})}$

La segunda oración tiene el mismo valor de verdad pero sigue la sintaxis restringida. Suponer que las fórmulas booleanas completamente cuantificadas están en forma normal prenex es una característica frecuente de las demostraciones.

Solucionadores QBF

Ingenuo

Existe un algoritmo recursivo simple para determinar si un QBF está en TQBF (es decir, es verdadero). Dado un QBF

${\displaystyle Q_{1}x_{1}Q_{2}x_{2}\cdots Q_{n}x_{n}\phi (x_{1},x_{2},\dots ,x_{n}).}$

Si la fórmula no contiene cuantificadores, podemos simplemente devolver la fórmula. De lo contrario, quitamos el primer cuantificador y verificamos ambos valores posibles para la primera variable:

${\displaystyle A=Q_{2}x_{2}\cdots Q_{n}x_{n}\phi (0,x_{2},\dots ,x_{n}),}$

${\displaystyle B=Q_{2}x_{2}\cdots Q_{n}x_{n}\phi (1,x_{2},\dots ,x_{n}).}$

Si , entonces devuelve . Si , entonces devuelve . ^[4] ${\displaystyle Q_{1}=\exists }$ ${\displaystyle A\lor B}$ ${\displaystyle Q_{1}=\forall }$ ${\displaystyle A\land B}$

¿Qué tan rápido se ejecuta este algoritmo? Para cada cuantificador en el QBF inicial, el algoritmo realiza dos llamadas recursivas solo en un subproblema linealmente más pequeño. Esto le da al algoritmo un tiempo de ejecución exponencial O(2 ⁿ ) . ^{[ cita requerida ]}

¿Cuánto espacio utiliza este algoritmo? En cada invocación del algoritmo, necesita almacenar los resultados intermedios del cálculo de A y B. Cada llamada recursiva quita un cuantificador, por lo que la profundidad recursiva total es lineal en el número de cuantificadores. Las fórmulas que carecen de cuantificadores se pueden evaluar en un espacio logarítmico en el número de variables. El QBF inicial estaba completamente cuantificado, por lo que hay al menos tantos cuantificadores como variables. Por lo tanto, este algoritmo utiliza un espacio O ( n + log n ) = O ( n ). Esto hace que el lenguaje TQBF sea parte de la clase de complejidad PSPACE . ^{[ cita requerida ]}

Lo último

A pesar de la completitud PSPACE de QBF, se han desarrollado muchos solucionadores para resolver estas instancias. (Esto es análogo a la situación con SAT , la versión de cuantificador existencial único; aunque es NP-completo , todavía es posible resolver muchas instancias de SAT de manera heurística). ^{[5] [6]} El caso donde solo hay 2 cuantificadores, conocido como 2QBF, ha recibido especial atención. ^{[7] [ palabras ambiguas ]}

La competición de solucionadores QBF QBFEVAL se ha estado realizando más o menos anualmente desde 2004; ^{[5] [6]} los solucionadores deben leer instancias en formato QDIMACS y en los formatos QCIR o QAIGER. ^[8] Los solucionadores QBF de alto rendimiento generalmente usan QDPLL (una generalización de DPLL ) o CEGAR. ^{[5] [6] [7]} La ​​investigación sobre la resolución de QBF comenzó con el desarrollo de DPLL de retroceso para QBF en 1998, seguido por la introducción del aprendizaje de cláusulas y la eliminación de variables en 2002; ^[9] por lo tanto, en comparación con la resolución SAT, que ha estado en desarrollo desde la década de 1960, QBF es un campo de investigación relativamente joven a partir de 2017. ^{[9] [ palabras ambiguas ]}

Algunos solucionadores QBF destacados incluyen:

• CADET, que resuelve fórmulas booleanas cuantificadas restringidas a una alternancia de cuantificadores (con la capacidad de calcular funciones de Skolem ), basada en la determinización incremental ^{[ aclaración necesaria ]} y con la capacidad de probar sus respuestas. ^[10]
• CAQE - un solucionador basado en CEGAR para fórmulas booleanas cuantificadas; ganador de las ediciones recientes de QBFEVAL. ^[11]
• DepQBF: un solucionador basado en búsquedas para fórmulas booleanas cuantificadas ^[12]
• sKizzo: el primer solucionador que utiliza skolemización simbólica, extrae certificados de satisfacibilidad, utiliza un motor de inferencia híbrido, implementa ramificación abstracta, maneja cuantificadores limitados y enumera asignaciones válidas, y ganador de QBFEVAL 2005, 2006 y 2007. ^[13]

Aplicaciones

Los solucionadores QBF se pueden aplicar a la planificación (en inteligencia artificial), incluida la planificación segura; esta última es fundamental en aplicaciones de robótica. ^[14] Los solucionadores QBF también se pueden aplicar a la verificación de modelos acotados , ya que proporcionan una codificación más corta que la que sería necesaria para un solucionador basado en SAT. ^[14]

La evaluación de un QBF puede verse como un juego de dos jugadores entre un jugador que controla variables cuantificadas existencialmente y un jugador que controla variables cuantificadas universalmente. Esto hace que los QBF sean adecuados para codificar problemas de síntesis reactiva . ^[14] De manera similar, los solucionadores de QBF se pueden utilizar para modelar juegos adversarios en la teoría de juegos . Por ejemplo, los solucionadores de QBF se pueden utilizar para encontrar estrategias ganadoras para juegos de geografía , que luego se pueden jugar automáticamente de forma interactiva. ^[15]

Los solucionadores QBF se pueden utilizar para la comprobación de equivalencia formal y también se pueden utilizar para sintetizar funciones booleanas. ^[14]

Otros tipos de problemas que pueden codificarse como QBF incluyen:

• Detectar si una cláusula en una fórmula insatisfactoria en forma normal conjuntiva pertenece a algún subconjunto mínimamente insatisfactorio ^{[9] [16]} y si una cláusula en una fórmula satisfacible pertenece a un subconjunto máximamente satisfacible ^[16]
• Codificaciones de planificación conforme ^{[9] [ aclaración necesaria ]}
• Problemas relacionados con ASP ^{[9] [ aclaración necesaria ]}
• Argumentación abstracta ^{[9] [ aclaración necesaria ]}
• Comprobación del modelo de lógica temporal lineal ^{[9] [ aclaración necesaria ]}
• Inclusión en lenguaje de autómatas finitos no deterministas ^{[9] [ aclaración necesaria ]}
• Síntesis y fiabilidad de sistemas distribuidos ^{[9] [ aclaración necesaria ]}

Extensiones

En QBFEVAL 2020, se introdujo una "vía DQBF" en la que se permitió que las instancias tuvieran cuantificadores Henkin (expresados ​​en formato DQDIMACS). ^[8]

PSPACE-completitud

El lenguaje TQBF sirve en la teoría de la complejidad como el problema PSPACE-completo canónico . Ser PSPACE-completo significa que un lenguaje está en PSPACE y que el lenguaje también es PSPACE-hard . El algoritmo anterior muestra que TQBF está en PSPACE. Demostrar que TQBF es PSPACE-hard requiere demostrar que cualquier lenguaje en la clase de complejidad PSPACE se puede reducir a TQBF en tiempo polinomial. Es decir,

${\displaystyle \forall L\in {\mathsf {PSPACE}},L\leq _{p}\mathrm {TQBF} .}$

Esto significa que, para un lenguaje PSPACE L, se puede decidir si una entrada x está en L verificando si está en TQBF, para alguna función f que se requiere ejecutar en tiempo polinomial (en relación con la longitud de la entrada). Simbólicamente, ${\displaystyle f(x)}$

${\displaystyle x\in L\iff f(x)\in \mathrm {TQBF} .}$

Para demostrar que TQBF es PSPACE-hard, se requiere la especificación de f .

Por lo tanto, supongamos que L es un lenguaje PSPACE. Esto significa que L puede decidirse mediante una máquina de Turing determinista de espacio polinomial (DTM). Esto es muy importante para la reducción de L a TQBF, porque las configuraciones de cualquier máquina de Turing de este tipo se pueden representar como fórmulas booleanas, con variables booleanas que representan el estado de la máquina, así como el contenido de cada celda en la cinta de la máquina de Turing, con la posición de la cabeza de la máquina de Turing codificada en la fórmula por el orden de la fórmula. En particular, nuestra reducción utilizará las variables y , que representan dos configuraciones posibles de la DTM para L, y un número natural t, para construir una QBF que es verdadera si y solo si la DTM para L puede pasar de la configuración codificada en a la configuración codificada en en no más de t pasos. La función f , entonces, construirá a partir del DTM para L un QBF , donde es la configuración inicial del DTM, es la configuración de aceptación del DTM, y T es el número máximo de pasos que el DTM podría necesitar para moverse de una configuración a la otra. Sabemos que T = O (exp( n k )) para algún k , donde n es la longitud de la entrada, porque esto limita el número total de configuraciones posibles del DTM relevante. Por supuesto, el DTM no puede dar más pasos que las configuraciones posibles a alcanzar a menos que entre en un bucle, en cuyo caso nunca alcanzará de todos modos. ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle \phi _{c_{1},c_{2},t}}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle \phi _{c_{\text{start}},c_{\text{accept}},T}}$ ${\displaystyle c_{start}}$ ${\displaystyle c_{\text{accept}}}$ ${\displaystyle c_{\mathrm {accept} }}$ ${\displaystyle c_{\mathrm {accept} }}$

En esta etapa de la prueba, ya hemos reducido la cuestión de si una fórmula de entrada w (codificada, por supuesto, en ) está en L a la cuestión de si el QBF , es decir, , está en TQBF. El resto de esta prueba demuestra que f se puede calcular en tiempo polinomial. ${\displaystyle c_{\text{start}}}$ ${\displaystyle \phi _{c_{\text{start}},c_{\text{accept}},T}}$ ${\displaystyle f(w)}$

Para , el cálculo de es sencillo: una de las configuraciones cambia a la otra en un solo paso o no lo hace. Como la máquina de Turing que representa nuestra fórmula es determinista, esto no presenta ningún problema. ${\displaystyle t=1}$ ${\displaystyle \phi _{c_{1},c_{2},t}}$

Para , el cálculo de implica una evaluación recursiva, buscando un denominado "punto medio" . En este caso, reescribimos la fórmula de la siguiente manera: ${\displaystyle t>1}$ ${\displaystyle \phi _{c_{1},c_{2},t}}$ ${\displaystyle m_{1}}$

${\displaystyle \phi _{c_{1},c_{2},t}=\exists m_{1}(\phi _{c_{1},m_{1},\lceil t/2\rceil }\wedge \phi _{m_{1},c_{2},\lceil t/2\rceil }).}$

Esto convierte la cuestión de si se puede llegar en t pasos en la cuestión de si se llega a un punto medio en pasos, que a su vez llega en pasos. La respuesta a la última pregunta, por supuesto, da la respuesta a la primera. ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle c_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle t/2}$ ${\displaystyle c_{2}}$ ${\displaystyle t/2}$

Ahora bien, t solo está limitado por T, que es exponencial (y por lo tanto no polinomial) en la longitud de la entrada. Además, cada capa recursiva prácticamente duplica la longitud de la fórmula. (La variable es solo un punto medio; para t mayor, hay más paradas en el camino, por así decirlo). Por lo tanto, el tiempo requerido para evaluar recursivamente de esta manera también podría ser exponencial, simplemente porque la fórmula podría volverse exponencialmente grande. Este problema se resuelve cuantificando universalmente utilizando variables y sobre los pares de configuración (por ejemplo, ), lo que evita que la longitud de la fórmula se expanda debido a las capas recursivas. Esto produce la siguiente interpretación de : ${\displaystyle m_{1}}$ ${\displaystyle \phi _{c_{1},c_{2},t}}$ ${\displaystyle c_{3}}$ ${\displaystyle c_{4}}$ ${\displaystyle \{(c_{1},m_{1}),(m_{1},c_{2})\}}$ ${\displaystyle \phi _{c_{1},c_{2},t}}$

${\displaystyle \phi _{c_{1},c_{2},t}=\exists m_{1}\forall (c_{3},c_{4})\in \{(c_{1},m_{1}),(m_{1},c_{2})\}(\phi _{c_{3},c_{4},\lceil t/2\rceil }).}$

Esta versión de la fórmula puede calcularse en tiempo polinómico, ya que cualquier instancia de la misma puede calcularse en tiempo polinómico. El par ordenado cuantificado universalmente simplemente nos dice que cualquiera sea la elección que se haga de , . ${\displaystyle (c_{3},c_{4})}$ ${\displaystyle \phi _{c_{1},c_{2},t}\iff \phi _{c_{3},c_{4},\lceil t/2\rceil }}$

Por lo tanto, TQBF es PSPACE-hard. Junto con el resultado anterior de que TQBF está en PSPACE, esto completa la prueba de que TQBF es un lenguaje PSPACE-completo. ${\displaystyle \forall L\in {\mathsf {PSPACE}},L\leq _{p}\mathrm {TQBF} }$

(Esta prueba sigue a Sipser 2006 pp. 310–313 en todos los puntos esenciales. Papadimitriou 1994 también incluye una prueba).

Miscelánea

• Un subproblema importante en TQBF es el problema de satisfacibilidad booleana . En este problema, desea saber si una fórmula booleana dada puede hacerse verdadera con alguna asignación de variables. Esto es equivalente al TQBF que utiliza solo cuantificadores existenciales: Este es también un ejemplo del resultado más grande NP ⊆ PSPACE que se desprende directamente de la observación de que un verificador de tiempo polinomial para una prueba de un lenguaje aceptado por una NTM ( máquina de Turing no determinista ) requiere espacio polinomial para almacenar la prueba. ${\displaystyle \phi }$ $${\displaystyle \exists x_{1}\cdots \exists x_{n}\phi (x_{1},\ldots ,x_{n})}$$
• Cualquier clase en la jerarquía polinómica ( PH ) tiene TQBF como un problema difícil. En otras palabras, para la clase que comprende todos los lenguajes L para los cuales existe una TM polinómica V, un verificador, tal que para todas las entradas x y alguna constante i, que tiene una formulación QBF específica que se da como tal que donde los son vectores de variables booleanas. $${\displaystyle x\in L\Leftrightarrow \exists y_{1}\forall y_{2}\cdots Q_{i}y_{i}\ V(x,y_{1},y_{2},\dots ,y_{i})\ =\ 1}$$ $${\displaystyle \exists \phi }$$ ${\displaystyle \exists {\vec {x_{1}}}\forall {\vec {x_{2}}}\cdots Q_{i}{\vec {x_{i}}}\ \phi ({\vec {x_{1}}},{\vec {x_{2}}},\dots ,{\vec {x_{i}}})\ =\ 1}$ ${\displaystyle {\vec {x_{i}}}}$
• Es importante señalar que, si bien el lenguaje TQBF se define como la colección de fórmulas booleanas cuantificadas verdaderas, la abreviatura TQBF se utiliza a menudo (incluso en este artículo) para referirse a una fórmula booleana totalmente cuantificada, a menudo denominada simplemente QBF (fórmula booleana cuantificada, entendida como "totalmente" o "completamente" cuantificada). Es importante distinguir contextualmente entre los dos usos de la abreviatura TQBF al leer la literatura.
• Un TQBF puede considerarse como un juego entre dos jugadores, con movimientos alternados. Las variables cuantificadas existencialmente son equivalentes a la noción de que un jugador puede realizar un movimiento en un turno. Las variables cuantificadas universalmente significan que el resultado del juego no depende del movimiento que realice un jugador en ese turno. Además, un TQBF cuyo primer cuantificador es existencial corresponde a un juego de fórmula en el que el primer jugador tiene una estrategia ganadora.
• Un TQBF cuya fórmula cuantificada está en 2-CNF puede resolverse en tiempo lineal mediante un algoritmo que implica un análisis de conectividad fuerte de su gráfico de implicación . El problema de 2-satisfacibilidad es un caso especial de TQBF para estas fórmulas, en el que cada cuantificador es existencial. ^{[17] [18]}
• Hay un tratamiento sistemático de versiones restringidas de fórmulas booleanas cuantificadas (que brindan clasificaciones de tipo Schaefer) proporcionado en un artículo expositivo de Hubie Chen. ^[19]
• D. Lichtenstein demostró que el TQBF planar, que generaliza el SAT planar , es PSPACE-completo. ^[20]

Notas y referencias

1. M. Garey y D. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman, San Francisco, California. ISBN 0-7167-1045-5.
2. A. Chandra, D. Kozen y L. Stockmeyer (1981). "Alternancia". Revista de la ACM . 28 (1): 114–133. doi : 10.1145/322234.322243 . S2CID  238863413.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Adi Shamir (1992). "Ip = Pspace". Revista de la ACM . 39 (4): 869–877. doi : 10.1145/146585.146609 . S2CID  315182.
4. Arora, Sanjeev; Barak, Boaz (2009), "Complejidad espacial", Computational Complexity , Cambridge: Cambridge University Press, págs. 78-94, doi :10.1017/cbo9780511804090.007, ISBN 978-0-511-80409-0, S2CID  262800930 , consultado el 26 de mayo de 2021
5. "Página de inicio de QBFEVAL". www.qbflib.org . Consultado el 13 de febrero de 2021 .
6. "Solucionadores QBF | Beyond NP". beyondnp.org . Consultado el 13 de febrero de 2021 .
7. Balabanov, Valeriy; Roland Jiang, Jie-Hong; Scholl, Christoph; Mishchenko, Alan; K. Brayton, Robert (2016). "2QBF: desafíos y soluciones" (PDF) . Conferencia internacional sobre teoría y aplicaciones de pruebas de satisfacibilidad : 453–459. Archivado (PDF) desde el original el 13 de febrero de 2021 – vía SpringerLink.
8. "QBFEVAL'20". www.qbflib.org . Consultado el 29 de mayo de 2021 .
9. Lonsing, Florian (diciembre de 2017). "Introducción a la resolución de QBF" (PDF) . www.florianlonsing.com . Consultado el 29 de mayo de 2021 .
10. Rabe, Markus N. (15 de abril de 2021), MarkusRabe / cadete , consultado el 6 de mayo de 2021
11. Tentrup, Leander (6 de mayo de 2021), ltentrup / caqe , consultado el 6 de mayo de 2021
12. "Solucionador DepQBF". lonsing.github.io . Consultado el 6 de mayo de 2021 .
13. "sKizzo - un solucionador de QBF". www.skizzo.site . Consultado el 6 de mayo de 2021 .
14. Shukla, Ankit; Biere, Armin; Seidl, Martina; Pulina, Luca (2019). Una encuesta sobre aplicaciones de fórmulas booleanas cuantificadas (PDF) . 2019 IEEE 31st International Conference on Tools for Artificial Intelligence. págs. 78–84. doi :10.1109/ICTAI.2019.00020 . Consultado el 29 de mayo de 2021 .
15. Shen, Zhihe. Uso de solucionadores QBF para resolver juegos y rompecabezas (PDF) (Tesis). Boston College.
16. Janota, Mikoláš; Marques-Silva, Joao (2011). Sobre la decisión de la membresía de MUS con QBF. Principios y práctica de la programación con restricciones – CP 2011. Vol. 6876. págs. 414–428. doi :10.1007/978-3-642-23786-7_32. ISBN 978-3-642-23786-7.
17. Krom, Melven R. (1967). "El problema de decisión para una clase de fórmulas de primer orden en las que todas las disyunciones son binarias". 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). "Un algoritmo de tiempo lineal para probar la verdad de ciertas fórmulas booleanas cuantificadas" (PDF) . Information Processing Letters . 8 (3): 121–123. doi :10.1016/0020-0190(79)90002-4..
19. Chen, Hubie (diciembre de 2009). "Un encuentro entre lógica, complejidad y álgebra". Encuestas de computación de la ACM . 42 (1). ACM: 1–32. arXiv : cs/0611018 . doi :10.1145/1592451.1592453. S2CID  11975818.
20. Lichtenstein, David (1 de mayo de 1982). "Fórmulas planares y sus usos". Revista SIAM de informática . 11 (2): 329–343. doi :10.1137/0211025. ISSN  0097-5397. S2CID  207051487.

• Fortnow y Homer (2003) proporcionan algunos antecedentes históricos sobre PSPACE y TQBF.
• Zhang (2003) proporciona algunos antecedentes históricos de las fórmulas booleanas.
• Arora, Sanjeev. (2001). COS 522: Computational Complexity. Notas de clase, Princeton University. Consultado el 10 de octubre de 2005.
• Fortnow, Lance y Steve Homer. (2003, junio). Una breve historia de la complejidad computacional. Boletín de la Asociación Europea de Ciencias Informáticas Teóricas , The Computational Complexity Column, 80. Consultado el 14 de mayo de 2024.
• Papadimitriou, CH (1994). Complejidad computacional. Lectura: Addison-Wesley.
• Sipser, Michael. (2006). Introducción a la teoría de la computación. Boston: Thomson Course Technology.
• Zhang, Lintao. (2003). Búsqueda de la verdad: técnicas para la satisfacibilidad de fórmulas booleanas. Recuperado el 10 de octubre de 2005.

Véase también

• Teorema de Cook-Levin , que establece que SAT es NP-completo
• Geografía generalizada

Enlaces externos

• La biblioteca de fórmulas booleanas cuantificadas (QBFLIB)
• Taller internacional sobre fórmulas booleanas cuantificadas