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 de satisfacibilidad booleano (SAT) se puede resolver 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 polinomial no determinista, 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 polinomial en su segundo nivel. Tal colapso se cree improbable, por lo que el teorema es generalmente visto por los teóricos de la complejidad 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 aleatorizado ( 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 debe su nombre a Richard M. Karp y Richard J. Lipton , quienes lo demostraron por primera vez en 1980. (Su prueba original colapsó PH a , pero Michael Sipser la mejoró a ). ${\displaystyle \Sigma _{3}}$ ${\displaystyle \Sigma _{2}}$

Las variantes del teorema establecen que, bajo el mismo supuesto, MA = AM y PH colapsa a S^Pág.
₂clase de complejidad. Se pueden sacar conclusiones más sólidas si se supone que PSPACE o alguna otra clase 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.

Intuición

Supongamos que no sólo existen circuitos de tamaño polinómico para SAT, sino que también se pueden construir mediante un algoritmo de tiempo polinómico. Entonces, esta suposición implica que SAT en sí podría resolverse mediante un algoritmo de tiempo polinómico que construye el circuito y luego lo aplica. Es decir, los circuitos construibles de manera eficiente 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 aún 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)}$

donde es cualquier predicado computable en tiempo polinomial. La potencia existencial del primer cuantificador en este predicado se puede utilizar para adivinar un circuito correcto para SAT, y la potencia universal del segundo cuantificador se puede utilizar para verificar que el circuito es correcto. Una vez que se adivina y verifica este circuito, el algoritmo en clase puede usarlo como una subrutina para resolver otros problemas. ${\displaystyle \psi }$ ${\displaystyle \Sigma _{2}}$

Autorreducibilidad

Para entender 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 dado, y mostramos que este problema de prueba de circuito pertenece a . Es decir, existe un predicado computable en tiempo polinomial V tal que c es un circuito correcto si y solo si, para todo z acotado polinomialmente , 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 verdadero
• Para cada instancia s de SAT para la cual c ( s ) es verdadera, s debe ser solucionable.

La primera de estas dos propiedades ya se encuentra 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 es solucionable, podemos encontrar casi con la misma rapidez una solución explícita para la instancia. Para encontrar una solución para una instancia s , elija una de las variables booleanas x que se ingresan en s y haga 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 han construido estas dos instancias más pequeñas, aplique la prueba de solubilidad a cada una de ellas. Si una de estas dos pruebas devuelve que la instancia más pequeña es satisfacible, continúe resolviendo esa instancia hasta que se haya derivado una solución completa.

Para utilizar la autorreducibilidad para comprobar la segunda propiedad de un circuito correcto para SAT, la 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 .

De esta forma podemos comprobar si c es un circuito válido para resolver SAT. ${\displaystyle \Pi _{1}}$

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

Demostración del teorema de Karp-Lipton

El teorema de Karp-Lipton puede reformularse como resultado de fórmulas booleanas con cuantificadores acotados polinómicamente. 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órmula se puede transformar en tiempo polinomial en una fórmula equivalente en la que los cuantificadores aparecen en orden opuesto; dicha fórmula pertenece a . Nótese 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 válido c ) 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 utilizando la autorreducibilidad, como se describió anteriormente. Esta fórmula equivalente tiene sus cuantificadores en el orden opuesto, 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 La repetición de 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, mostrando que ${\displaystyle \Sigma _{2}=\Pi _{2}.}$ ${\displaystyle PH=\Sigma _{2}.}$

Otra prueba y SPág. 2

Supongamos que . Por lo tanto, existe una familia de circuitos que resuelve la satisfacibilidad en una entrada de longitud n . Al utilizar la autorreducibilidad, existe una familia de circuitos que genera una asignación satisfactoria en instancias verdaderas. ${\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 puede considerarse una instancia de SAT (por el teorema de Cook-Levin ), existe un circuito , que depende 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 haga que sea 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}}$

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

AM = MA

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

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

(ver protocolo Arturo-Merlín ).

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 anteriormente reescribir 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 de los circuitos: 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 no está 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 la 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 demuestra un 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 lo 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 a: para cualquier k , existe un lenguaje . ${\displaystyle L\in {\mathsf {S}}_{2}^{P}-{\mathsf {SIZE}}(n^{k})}$

También se sabe que PP no está contenido en , lo que fue demostrado por 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}}}$(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 permanente, véase P/poly )

Las contenciones son igualdades y las obtenemos por 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 polinomial, 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 uniforme y no uniforme", 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 , 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.