Teorema de Karp-Lipton

En la teoría de la complejidad , el teorema de Karp-Lipton establece que si el problema de satisfacibilidad booleana (SAT) puede resolverse mediante circuitos booleanos con un número polinomial de puertas lógicas, entonces

${\displaystyle \Pi _{2}=\Sigma _{2}\,}$y por lo tanto${\displaystyle {\mathsf {PH}}=\Sigma _{2}.\,}$

Es decir, si asumimos que NP , la clase de problemas polinomiales no deterministas, puede estar contenida en la clase de complejidad polinomial no uniforme P/poly , entonces esta suposición implica el colapso de la jerarquía polinomial en su segundo nivel. Se cree que tal colapso es improbable, por lo que los teóricos de la complejidad generalmente ven el teorema como evidencia de la inexistencia de circuitos de tamaño polinomial para SAT o para otros problemas NP-completos . Una prueba de que tales circuitos no existen implicaría que P ≠ NP . Como P/poly contiene todos los problemas resolubles en tiempo polinomial aleatorio ( teorema de Adleman ), el teorema también es evidencia de que el uso de la aleatorización no conduce a algoritmos de tiempo polinomial para problemas NP-completos.

El teorema de Karp-Lipton recibe su nombre de Richard M. Karp y Richard J. Lipton , quienes lo demostraron por primera vez en 1980. (Su demostración original colapsó PH a${\displaystyle \Sigma _{3}}$, pero Michael Sipser lo mejoró a${\displaystyle \Sigma _{2}}$.)

Variantes del teorema afirman que, bajo la misma suposición, MA = AM y PH colapsa a la clase de complejidad S ^P _2. Se pueden obtener conclusiones más sólidas si se supone que PSPACE u otras clases de complejidad tienen circuitos de tamaño polinomial; véase P/poly . Si se supone que NP es un subconjunto de BPP (que es un subconjunto de P/poly), entonces la jerarquía polinomial colapsa a BPP . ^{[ 1 ]} Si se supone que coNP es un subconjunto de NP/poly , entonces la jerarquía polinomial colapsa a su tercer nivel.

Supongamos que existen circuitos de tamaño polinomial para SAT, y que además pueden construirse mediante un algoritmo de tiempo polinomial. Esta suposición implica que SAT podría resolverse mediante un algoritmo de tiempo polinomial que construye el circuito y luego lo aplica. Es decir, la construcción eficiente de circuitos para SAT conduciría a un colapso más fuerte, P = NP.

La suposición del teorema de Karp-Lipton, de que estos circuitos existen, es más débil. Pero aún es posible que un algoritmo en la clase de complejidad${\displaystyle \Sigma _{2}}$adivinar un circuito correcto para SAT. La clase de complejidad${\displaystyle \Sigma _{2}}$describe problemas de la forma

${\displaystyle \exists x\forall y\;\psi (x,y)}$

dónde${\displaystyle \psi }$es cualquier predicado computable en tiempo polinomial. El poder existencial del primer cuantificador en este predicado se puede usar para adivinar un circuito correcto para SAT, y el poder universal del segundo cuantificador se puede usar para verificar que el circuito es correcto. Una vez que se adivina y verifica este circuito, el algoritmo en clase${\displaystyle \Sigma _{2}}$puede utilizarse como subrutina para resolver otros problemas.

Para comprender con más detalle la demostración de Karp-Lipton, consideramos el problema de probar si un circuito c es un circuito correcto para resolver instancias SAT de un tamaño dado, y mostramos que este problema de prueba de circuitos pertenece a${\displaystyle \Pi _{1}}$. Es decir, existe un predicado V computable en tiempo polinomial tal que c es un circuito correcto si y solo si , para todo z acotado polinomialmente , V ( c , z ) es verdadero.

El circuito c es un circuito correcto para SAT si satisface dos propiedades:

• Para cada par ( s , x ) donde s es una instancia de SAT y x es una solución a la instancia, c ( s ) debe ser verdadero.
• Para cada instancia s de SAT para la cual c ( s ) es verdadera, s debe ser resoluble.

La primera de estas dos propiedades ya se presenta en forma de problemas en clase.${\displaystyle \Pi _{1}}$Para verificar la segunda propiedad, utilizamos la propiedad de autorreducibilidad de SAT.

La autorreductibilidad describe el fenómeno de que, si podemos comprobar rápidamente si una instancia SAT es resoluble, podemos encontrar casi con la misma rapidez una solución explícita para dicha instancia. Para encontrar una solución a una instancia s , se elige una de las variables booleanas x que se introducen en s , y se crean dos instancias más pequeñas, _s₀ y s₁ , _donde sᵢ denota _la fórmula formada al sustituir x por la constante i . Una vez construidas estas dos instancias más pequeñas, se aplica la prueba de resolubilidad a cada una de ellas. Si una de estas dos pruebas indica que la instancia más pequeña es satisfacible, se continúa resolviendo dicha instancia hasta obtener una solución completa.

Para utilizar la autorreductibilidad para comprobar la segunda propiedad de un circuito correcto para SAT, lo reescribimos de la siguiente manera:

• Para cada instancia s de SAT para la cual c ( s ) es verdadera, el procedimiento de autorreducción descrito anteriormente encuentra una solución válida para s .

Por lo tanto, podemos probar en${\displaystyle \Pi _{1}}$si c es un circuito válido para resolver SAT.

Consulte la sección "Autorreducción aleatoria" para obtener más información.

El teorema de Karp-Lipton puede reformularse como un resultado sobre fórmulas booleanas con cuantificadores acotados polinomialmente. Problemas en${\displaystyle \Pi _{2}}$se describen mediante fórmulas de este tipo, con la sintaxis

${\displaystyle \phi =\forall x\exists y\;\psi (x,y)}$

dónde${\displaystyle \psi }$es un predicado computable en tiempo polinomial. El teorema de Karp-Lipton establece que este tipo de fórmula puede transformarse en tiempo polinomial en una fórmula equivalente en la que los cuantificadores aparecen en orden inverso; dicha fórmula pertenece a${\displaystyle \Sigma _{2}}$. Tenga en cuenta que la subfórmula

${\displaystyle s(x)=\exists y\;\psi (x,y)}$

es un ejemplo de SAT. Es decir, si c es un circuito válido para SAT, entonces esta subfórmula es equivalente a la fórmula no cuantificada c ( s ( x )). Por lo tanto, la fórmula completa para${\displaystyle \phi }$es equivalente (bajo el supuesto de que existe un circuito válido c ) a la fórmula

${\displaystyle \exists c\forall (x,z)\;V(c,z)\wedge c(s(x))\,}$

donde V es la fórmula utilizada para verificar que c realmente es un circuito válido mediante la autorreducción, como se describió anteriormente. Esta fórmula equivalente tiene sus cuantificadores en el orden opuesto, como se deseaba. Por lo tanto, la suposición de Karp-Lipton nos permite transponer el orden de los cuantificadores existenciales y universales en fórmulas de este tipo, mostrando que${\displaystyle \Sigma _{2}=\Pi _{2}.}$Repetir la transposición permite simplificar fórmulas con anidamiento más profundo a una forma en la que tienen un único cuantificador existencial seguido de un único cuantificador universal, lo que demuestra que${\displaystyle PH=\Sigma _{2}.}$

Asumir${\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}}$Por lo tanto, existe una familia de circuitos.${\displaystyle C_{n}}$que resuelve la satisfacibilidad en una entrada de longitud n . Utilizando la autorreducibilidad, existe una familia de circuitos${\displaystyle D_{n}}$lo que produce una asignación satisfactoria en instancias verdaderas.

Supongamos que L es un${\displaystyle \Pi _{2}}$colocar

${\displaystyle L=\{z:\forall x.\exists y.\phi (x,y,z)\}\,}$

Desde${\displaystyle \exists y.\phi (x,y,z)}$puede considerarse una instancia de SAT (por el teorema de Cook-Levin ), existe un circuito${\displaystyle D_{n}}$, Dependiendo de${\displaystyle n=|z|}$, de tal manera que la fórmula que define L es equivalente a

Además, el circuito puede adivinarse mediante cuantificación existencial :

Obviamente ( 1 ) implica ( 2 ). Si (1) es falso, entonces${\displaystyle \neg \exists y.\phi (x,y,z)}$En este caso, ningún circuito D puede generar una asignación.${\displaystyle \phi (x,D(x,z),z)\;}$verdadero.

La prueba ha demostrado que un${\displaystyle \Pi _{2}}$colocar${\displaystyle L}$está en${\displaystyle \Sigma _{2}}$.

Es más, si el${\displaystyle \Pi _{2}}$Si la fórmula es verdadera, entonces el circuito D funcionará contra cualquier x . Si la${\displaystyle \Pi _{2}}$La fórmula es falsa, entonces x haciendo que la fórmula (1) sea falsa funcionará en contra de cualquier circuito. Esta propiedad significa un colapso más fuerte, a saber, a la clase de complejidad S ^P ₂ (es decir,${\displaystyle \Pi _{2}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}}$). Fue observado por Sengupta. ^{[ 2 ]}

El teorema de Kannan ^{[ 4 ]} establece que para cualquier k fijo existe un lenguaje${\displaystyle L}$en${\displaystyle \Sigma _{2}}$, que no está en SIZE (n ^k ) (Esta es una declaración diferente a${\displaystyle \Sigma _{2}\not \subseteq {\mathsf {P/poly}}}$, que actualmente está abierto y afirma que existe un único lenguaje que no está en SIZE (n ^k ) para ningún k ). Es una simple cota inferior de circuito .

Esquema de la demostración:

Existe un lenguaje${\displaystyle L\in \Sigma _{4}-{\mathsf {SIZE}}(n^{k})}$(La demostración utiliza la técnica de diagonalización ). Consideremos dos casos:

• Si${\displaystyle {\mathsf {SAT}}\notin {\mathsf {P/poly}}}$entonces${\displaystyle {\mathsf {SAT}}\notin {\mathsf {TAMAÑO}}(n^{k})}$y el teorema queda demostrado.
• Si${\displaystyle {\mathsf {SAT}}\in {\mathsf {P/poly}}}$, entonces por el teorema de Karp-Lipton,${\displaystyle \Sigma _{4}=\Sigma _{2}}$y por lo tanto${\displaystyle L\in \Sigma _{2}-{\mathsf {SIZE}}(n^{k})}$.

Una versión más fuerte del teorema de Karp-Lipton fortalece el teorema de Kannan a: para cualquier k , existe un lenguaje${\displaystyle L\in {\mathsf {S}}_{2}^{P}-{\mathsf {SIZE}}(n^{k})}$.

También se sabe que el PP no está contenido en${\displaystyle {\mathsf {SIZE}}(n^{k})}$, lo cual fue probado por Vinodchandran. ^{[ 5 ]} Prueba: ^{[ 6 ]}

• Si${\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {P/poly}}}$entonces${\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {SIZE}}(n^{k})}$.
• De lo contrario,${\displaystyle {\mathsf {P^{\#P}}}\subseteq {\mathsf {P/poly}}}$. Desde

${\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PP}}\supseteq {\mathsf {MA}}}$(por propiedad de MA )

${\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PH}}\supseteq \Sigma _{2}\supseteq {\mathsf {MA}}}$(por el teorema de Toda y la propiedad de MA)

${\displaystyle {\mathsf {P^{\#P}}}={\mathsf {MA}}}$(Se deduce de la suposición de que se utiliza un protocolo interactivo para lo permanente, véase P/poly )

las contenciones son igualdades y obtenemos${\displaystyle {\mathsf {PP}}=\Sigma _{2}\not \subseteq {\mathsf {SIZE}}(n^{k})}$por el teorema de Kannan.

• Karp, RM ; Lipton, RJ (1980), "Algunas conexiones entre clases de complejidad uniformes y no uniformes", Actas del Duodécimo Simposio Anual de la ACM sobre Teoría de la Computación , págs. 302–309 , doi : 10.1145/800141.804678 , ISBN  0-89791-017-6, S2CID 1458043 .

• Karp, RM ; Lipton, RJ (1982), "Máquinas de Turing que aceptan consejos", L'Enseignement Mathématique , 28 : 191–209 , doi : 10.5169/seals-52237.