Teorema de Karp-Lipton

On collapse of the polynomial hierarchy if NP is in non-uniform polynomial time class

En teoría de la complejidad , el teorema de Karp-Lipton establece que si el problema booleano de satisfacibilidad (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 de tiempo polinómicos no deterministas, puede estar contenida en la clase de complejidad de tiempo polinomial no uniforme P/poly , entonces esta suposición implica el colapso de la jerarquía polinómica en su segundo nivel. Se cree que tal colapso es poco probable, por lo que los teóricos de la complejidad generalmente ven el teorema como evidencia de la inexistencia de circuitos de tamaño polinómico 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 que se pueden resolver 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 polinómico para problemas NP-completos.

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

Las variantes del teorema establecen que, bajo el mismo supuesto, MA = AM y PH colapsa a SP 2clase de complejidad. Es posible sacar conclusiones más sólidas si se supone que PSPACE o algunas otras clases de complejidad tienen circuitos de tamaño polinómico; ver P/poli . Si se supone que NP es un subconjunto de BPP (que es un subconjunto de P/poly), entonces la jerarquía polinómica colapsa a BPP . ^[1] Si se supone que coNP es un subconjunto de NP/poly , entonces la jerarquía polinómica colapsa a su tercer nivel.

Intuición

Supongamos que no sólo existen circuitos de tamaño polinomial para SAT, sino que también podrían construirse mediante un algoritmo de tiempo polinómico. Entonces esta suposición implica que el propio SAT podría resolverse mediante un algoritmo de tiempo polinómico que construye el circuito y luego lo aplica. Es decir, circuitos construibles eficientemente para SAT conducirían 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 todavía es posible que un algoritmo de la clase de complejidad adivine un circuito correcto para SAT. La clase de complejidad describe problemas de la forma ${\displaystyle \Sigma _{2}}$ ${\displaystyle \Sigma _{2}}$

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

¿Dónde está cualquier predicado computable en tiempo polinomial? La potencia existencial del primer cuantificador en este predicado se puede usar para adivinar un circuito correcto para SAT, y la potencia universal del segundo cuantificador se puede usar para verificar que el circuito es correcto. Una vez adivinado y verificado este circuito, el algoritmo en clase puede utilizarlo como subrutina para resolver otros problemas. ${\displaystyle \psi }$ ${\displaystyle \Sigma _{2}}$

Autoreducibilidad

Para comprender la prueba de Karp-Lipton con más detalle, consideramos el problema de probar si un circuito c es un circuito correcto para resolver instancias SAT de un tamaño determinado y demostramos que este problema de prueba de circuito pertenece a . Es decir, existe un predicado polinomial computable V tal que c es un circuito correcto si y sólo si, para todos los z polinomialmente acotados , V ( c , z ) es verdadero. ${\displaystyle \Pi _{1}}$

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 verdadera
• Para cada instancia s de SAT para la cual c ( s ) es verdadera, s debe tener solución.

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

La autorreducibilidad describe el fenómeno de que, si podemos probar rápidamente si una instancia SAT tiene solución, podemos encontrar casi con la misma rapidez una solución explícita para la instancia. Para encontrar una solución a una instancia s , elija una de las variables booleanas x que se ingresa a s y cree dos instancias más pequeñas s ₀ y s ₁ donde s _i denota la fórmula formada al reemplazar x con la constante i . Una vez que se hayan construido estas dos instancias más pequeñas, aplique la prueba de solubilidad a cada una de ellas. Si una de estas dos pruebas arroja que la instancia más pequeña es satisfactoria, continúe resolviendo esa instancia hasta que se haya obtenido una solución completa.

Para utilizar la autorreducibilidad para verificar 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 tanto, podemos probar si c es un circuito válido para resolver SAT. ${\displaystyle \Pi _{1}}$

Consulte Autoreducibilidad aleatoria para obtener más información.

Prueba del teorema de Karp-Lipton

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

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

donde es un predicado computable en tiempo polinomial. El teorema de Karp-Lipton establece que este tipo de fórmulas se pueden transformar en tiempo polinómico en una fórmula equivalente en la que los cuantificadores aparecen en orden opuesto; tal fórmula pertenece a . Tenga en cuenta que la subfórmula ${\displaystyle \psi }$ ${\displaystyle \Sigma _{2}}$

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

es una instancia 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 es equivalente (bajo el supuesto de que existe un circuito c válido ) a la fórmula ${\displaystyle \phi }$

${\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 que utiliza la autorreducibilidad, como se describió anteriormente. Esta fórmula equivalente tiene sus cuantificadores en el orden inverso, como se desea. Por lo tanto, el supuesto de Karp-Lipton nos permite transponer el orden de los cuantificadores existenciales y universales en fórmulas de este tipo, mostrando que 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 \Sigma _{2}=\Pi _{2}.}$ ${\displaystyle PH=\Sigma _{2}.}$

Otra prueba y SP 2

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

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

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

Dado que se puede considerar una instancia de SAT (según el teorema de Cook-Levin ), existe un circuito , dependiendo de , tal que la fórmula que define L es equivalente a ${\displaystyle \exists y.\phi (x,y,z)}$ ${\displaystyle D_{n}}$ ${\displaystyle n=|z|}$

Además, el circuito se puede adivinar con cuantificación existencial:

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

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

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

soy = ma

Una modificación ^[3] de la prueba anterior produce

${\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}\implies {\mathsf {AM}}={\mathsf {MA}}}$

(ver protocolo Arthur-Merlin ).

Supongamos que L está en AM , es decir:

${\displaystyle z\in L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\geq {\tfrac {2}{3}}}$

${\displaystyle z\notin L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\leq {\tfrac {1}{3}}}$

y como se reescribió anteriormente usando el circuito que genera una asignación satisfactoria si existe: ${\displaystyle \exists y.\phi (x,y,z)}$ ${\displaystyle D_{n}}$

${\displaystyle z\in L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\geq {\tfrac {2}{3}}}$

${\displaystyle z\notin L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\leq {\tfrac {1}{3}}}$

Ya que se puede adivinar: ${\displaystyle D_{n}}$

${\displaystyle z\in L\implies \exists D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\geq {\tfrac {2}{3}}}$

${\displaystyle z\notin L\implies \forall D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\leq {\tfrac {1}{3}}}$

lo que demuestra que está en la clase más pequeña MA . ${\displaystyle L}$

Aplicación a los límites inferiores del circuito: teorema de Kannan

El teorema de Kannan ^[4] establece que para cualquier k fijo existe un lenguaje en , que no está en TAMAÑO (n ^k ) (Esta es una afirmación diferente a , que actualmente está abierta y establece que existe un solo lenguaje que es no en TAMAÑO (n ^k ) para cualquier k ). Es un límite inferior de circuito simple . ${\displaystyle L}$ ${\displaystyle \Sigma _{2}}$ ${\displaystyle \Sigma _{2}\not \subseteq {\mathsf {P/poly}}}$

Esquema de prueba:

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

• Si entonces se prueba el teorema. ${\displaystyle {\mathsf {SAT}}\notin {\mathsf {P/poly}}}$ ${\displaystyle {\mathsf {SAT}}\notin {\mathsf {SIZE}}(n^{k})}$
• Si , entonces por el teorema de Karp-Lipton y por tanto . ${\displaystyle {\mathsf {SAT}}\in {\mathsf {P/poly}}}$ ${\displaystyle \Sigma _{4}=\Sigma _{2}}$ ${\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 para decir: 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 , como lo demostró Vinodchandran. ^[5] Prueba: ^[6] ${\displaystyle {\mathsf {SIZE}}(n^{k})}$

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

${\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}}}$(según el teorema de Toda y la propiedad de MA)

${\displaystyle {\mathsf {P^{\#P}}}={\mathsf {MA}}}$(se deriva de la suposición que utiliza el protocolo interactivo para permanente, consulte P/poly )

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

Referencias

1. S. Zachos , Cuantificadores y juegos probabilísticos, 1988
2. Jin Yi-Cai. [1], sección 6 ${\displaystyle S_{2}^{P}\subseteq {\mathsf {ZPP}}^{\mathsf {NP}}}$
3. V. Arvind, J. Köbler, U. Schöning , R. Schuler, Si NP tiene circuitos de tamaño polinómico, entonces MA = AM
4. Kannan, R. (1982). "Límites inferiores del tamaño del circuito y no reducibilidad a conjuntos dispersos". Información y Control . 55 (1–3): 40–56. doi :10.1016/S0019-9958(82)90382-5.
5. NV Vinodchandran, Una nota sobre la complejidad del circuito de PP
6. S. Aaronson , Los oráculos son sutiles pero no maliciosos

• Karp, RM ; Lipton, RJ (1980), "Algunas conexiones entre clases de complejidad uniformes y no uniformes", Actas del duodécimo simposio anual ACM sobre teoría de la computación , págs. 302–309, doi : 10.1145/800141.804678 , 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.