Verdadera fórmula booleana cuantificada

En la teoría de la complejidad computacional , el lenguaje TQBF es un lenguaje formal que consta de 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 vincula ), 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 dicha fórmula se evalúa como verdadera, entonces esa fórmula está en el lenguaje TQBF. También se le conoce como QSAT ( SAT Cuantificado ).

Descripción general

En la teoría de la complejidad computacional, el problema de 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 otra manera, 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 de PSPACE , la clase de problemas que pueden resolverse mediante una máquina de Turing determinista o no determinista en espacio polinomial y tiempo ilimitado. ^[1] Dada la fórmula en forma de árbol de sintaxis abstracta , el problema se puede resolver fácilmente mediante un conjunto de procedimientos mutuamente recursivos que evalúan la fórmula. Dicho algoritmo 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 siquiera se puede verificar una solución dada, en tiempo polinomial determinista o probabilístico (de hecho, a diferencia del problema de satisfacibilidad, no se conoce una manera de especificar una solución de manera sucinta). ). Se puede resolver utilizando una máquina de Turing alterna en tiempo lineal, ya que AP = PSPACE, donde AP es la clase de problemas que las máquinas alternas pueden resolver en tiempo polinomial. ^[2]

Cuando se mostró el resultado fundamental IP = PSPACE (ver sistema de prueba interactivo ), se hizo exhibiendo un sistema de prueba interactivo que podrí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 en tiempo polinomial que moverá todos los cuantificadores al frente de la fórmula y los hará alternar entre cuantificadores universales y existenciales. Hay 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 el número 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 sólo cuantificadores y una parte que contiene una fórmula booleana no cuantificada normalmente denominada . 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 prenexa 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 totalmente cuantificadas están en forma normal prenex es una característica frecuente de las pruebas.

Solucionadores QBF

Ingenuo

Existe un algoritmo recursivo simple para determinar si un QBF está en TQBF (es decir, es verdadero). Dado algo de 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, simplemente podemos devolver la fórmula. En caso contrario, quitamos el primer cuantificador y comprobamos 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 regresa . Si , entonces regresa . ^[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 necesaria ]}

¿Cuánto espacio utiliza este algoritmo? Dentro de cada invocación del algoritmo, es necesario almacenar los resultados intermedios de calcular A y B. Cada llamada recursiva toma 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 el espacio logarítmico en el número de variables. El QBF inicial se cuantificó completamente, por lo que hay al menos tantos cuantificadores como variables. Por tanto, este algoritmo utiliza el espacio O ( n + log n ) = O ( n ). Esto hace que el lenguaje TQBF forme parte de la clase de complejidad PSPACE . ^{[ cita necesaria ]}

Lo último

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

El concurso de solucionadores QBF QBFEVAL se lleva a cabo más o menos anualmente desde 2004; ^{[5] [6]} Se requieren solucionadores para 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 de 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 en 2017. ^{[9] [ palabras de comadreja ]}

Algunos solucionadores de QBF destacados incluyen:

• CADET, que resuelve fórmulas booleanas cuantificadas restringidas a una alternancia de cuantificadores (con capacidad de calcular funciones de Skolem ), basadas en determinización incremental ^{[ se necesita aclaración ]} y con capacidad de probar sus respuestas. ^[10]
• CAQE: un solucionador basado en CEGAR para fórmulas booleanas cuantificadas; ganador de las recientes ediciones de QBFEVAL. ^[11]
• DepQBF: un solucionador basado en búsquedas para fórmulas booleanas cuantificadas ^[12]
• sKizzo: el primer solucionador en utilizar eskolemización simbólica, extraer certificados de satisfacibilidad, utilizar un motor de inferencia híbrido, implementar ramificaciones abstractas, tratar con cuantificadores limitados y enumerar 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; este último es fundamental en las aplicaciones de la 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 existencialmente cuantificadas y un jugador que controla variables universalmente cuantificadas. Esto hace que los QBF sean adecuados para codificar problemas de síntesis reactiva . ^[14] De manera similar, los solucionadores QBF se pueden utilizar para modelar juegos adversarios en la teoría de juegos . Por ejemplo, los solucionadores 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 comprobar la equivalencia formal y también se pueden utilizar para sintetizar funciones booleanas. ^[14]

Otros tipos de problemas que se pueden codificar como QBF incluyen:

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

Extensiones

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

PSPACE-integridad

El lenguaje TQBF sirve en la teoría de la complejidad como el problema canónico completo de PSPACE . Ser PSPACE-completo significa que un idioma está en PSPACE y que el idioma también es PSPACE-duro . El algoritmo anterior muestra que TQBF está en PSPACE. Demostrar que TQBF es PSPACE-duro requiere demostrar que cualquier lenguaje en la clase de complejidad PSPACE se puede reducir a TQBF en tiempo polinómico. 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 deba ejecutarse 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 .

Entonces, supongamos que L es un lenguaje PSPACE. Esto significa que L puede decidirse mediante una máquina de Turing determinista en el espacio polinomial (DTM). Esto es muy importante para la reducción de L a TQBF, porque las configuraciones de cualquier Máquina de Turing 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 del cabezal de la máquina de Turing codificada en la fórmula mediante el orden de la fórmula. En particular, nuestra reducción utilizará las variables y , que representan dos posibles configuraciones del MDT para L, y un número natural t, para construir un QBF que es verdadero si y sólo si el MDT para L puede pasar de la configuración codificada en a la configuración codificada en no más de t pasos. La función f , entonces, se construirá a partir del DTM para La 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 pasar de una configuración a la otra. Sabemos que T = O (exp( n k )) para algunos k , donde n es la longitud de la entrada, porque esto limita el número total de configuraciones posibles del DTM relevante. Por supuesto, no puede llevar al DTM más pasos de los que pueden alcanzar las configuraciones posibles a menos que entre en un bucle, en cuyo caso nunca llegará 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 demostración, 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 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: o una de las configuraciones cambia a la otra en un paso o no. Dado que 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 el llamado "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 a la cuestión de si se alcanza un punto medio en pasos, que a su vez llega en pasos. La respuesta a la última pregunta, por supuesto, da 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, t sólo está limitado por T, que es exponencial (y por tanto no polinómico) en la longitud de la entrada. Además, cada capa recursiva prácticamente duplica la longitud de la fórmula. (La variable es sólo un punto medio; para mayor t, 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 usando variables y sobre los pares de configuración (por ejemplo, ), lo que evita que la longitud de la fórmula se expanda debido a 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 }).}$

De hecho, esta versión de la fórmula se puede calcular en tiempo polinomial, ya que cualquier instancia de ella se puede calcular en tiempo polinomial. El par ordenado universalmente cuantificado simplemente nos dice que cualquiera que sea la elección que se haga, . ${\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-duro. Junto con el resultado anterior de que TQBF está en PSPACE, esto completa la prueba de que TQBF es un lenguaje completo en PSPACE. ${\displaystyle \forall L\in {\mathsf {PSPACE}},L\leq _{p}\mathrm {TQBF} }$

(Esta prueba sigue a Sipser 2006 pp. 310-313 en todo lo esencial. 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 determinada se puede hacer verdadera con alguna asignación de variables. Esto es equivalente al TQBF usando solo cuantificadores existenciales: Este es también un ejemplo del resultado más amplio NP ⊆ PSPACE que se deriva 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 polinómico 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 un TM V poli-tiempo, 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 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 representar una fórmula booleana totalmente cuantificada, a menudo denominada simplemente QBF (cuantificación booleana). fórmula, entendida como "totalmente" o "totalmente" cuantificada). Es importante distinguir contextualmente entre los dos usos de la abreviatura TQBF al leer la literatura.
• Se puede considerar un TQBF como un juego que se juega entre dos jugadores, con movimientos alternos. Las variables existencialmente cuantificadas equivalen a la noción de que un movimiento está disponible para un jugador en un turno. Las variables universalmente cuantificadas significan que el resultado del juego no depende del movimiento que haga un jugador en ese turno. Asimismo, un TQBF cuyo primer cuantificador es existencial corresponde a un juego de fórmulas 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 fuerte análisis de conectividad de su gráfico de implicaciones . El problema de 2-satisfacibilidad es un caso especial de TQBF para estas fórmulas, en el que cada cuantificador es existencial. ^{[17] [18]}
• Existe un tratamiento sistemático de versiones restringidas de fórmulas booleanas cuantificadas (que dan clasificaciones de tipo Schaefer) proporcionadas en un artículo expositivo de Hubie Chen. ^[19]
• D. Lichtenstein demostró que Planar TQBF, que generaliza Planar SAT , 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 integridad NP . 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 = Pespacio". Revista de la ACM . 39 (4): 869–877. doi : 10.1145/146585.146609 . S2CID  315182.
4. Arora, Sanjeev; Barak, Boaz (2009), "Complejidad espacial", Complejidad computacional , 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 | Más allá de NP". más allá de np.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 las pruebas de satisfacción : 453–459. Archivado (PDF) desde el original el 13 de febrero de 2021, a través de 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 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) . 31ª Conferencia Internacional del IEEE 2019 sobre Herramientas para la Inteligencia Artificial. págs. 78–84. doi :10.1109/ICTAI.2019.00020 . Consultado el 29 de mayo de 2021 .
15. Shen, Zhihe. Uso de QBF Solvers para resolver juegos y acertijos (PDF) (Tesis). Boston College.
16. Janota, Mikoláš; Marqués-Silva, Joao (2011). Sobre la decisión de ser miembro de MUS con QBF. Principios y práctica de la programación de 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 determinadas fórmulas booleanas cuantificadas" (PDF) . Cartas de procesamiento de información . 8 (3): 121-123. doi :10.1016/0020-0190(79)90002-4..
19. Chen, Hubie (diciembre de 2009). "Un encuentro de lógica, complejidad y álgebra". Encuestas de Computación ACM . 42 (1). MCA: 1–32. arXiv : cs/0611018 . doi :10.1145/1592451.1592453. S2CID  11975818.
20. Lichtenstein, David (1 de mayo de 1982). "Fórmulas planas y sus usos". Revista SIAM de Computación . 11 (2): 329–343. doi :10.1137/0211025. ISSN  0097-5397. S2CID  207051487.

• Fortnow y Homer (2003) proporcionan algunos antecedentes históricos de PSPACE y TQBF.
• Zhang (2003) proporciona algunos antecedentes históricos de las fórmulas booleanas.
• Arora, Sanjeev. (2001). COS 522: Complejidad Computacional. Notas de conferencias, Universidad de Princeton. 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 Informática Teórica , 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: Tecnología del curso Thomson.
• Zhang, Lintao. (2003). Buscando la verdad: Técnicas de satisfacibilidad de fórmulas booleanas. Consultado el 10 de octubre de 2005.

Ver también

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

enlaces externos

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