Jerarquía polinómica

En la teoría de la complejidad computacional , la jerarquía polinomial (a veces llamada jerarquía de tiempo polinomial ) es una jerarquía de clases de complejidad que generalizan las clases NP y co-NP . ^{[ 1 ]} Cada clase en la jerarquía está contenida dentro de PSPACE . La jerarquía puede definirse usando máquinas oráculo o máquinas de Turing alternas . Es una contraparte con recursos limitados de la jerarquía aritmética y la jerarquía analítica de la lógica matemática . La unión de las clases en la jerarquía se denota PH .

Las clases dentro de la jerarquía presentan problemas completos (con respecto a reducciones en tiempo polinomial ) que determinan si se cumplen las fórmulas booleanas cuantificadas , para fórmulas con restricciones en el orden de los cuantificadores. Se sabe que la igualdad entre clases del mismo nivel o de niveles consecutivos en la jerarquía implicaría un "colapso" de la jerarquía a ese nivel.

Definiciones

Existen múltiples definiciones equivalentes de las clases de la jerarquía polinómica.

Definición de Oracle

Para la definición de oráculo de la jerarquía polinómica, defina

\Delta _{0}^{\mathrm {P} }:=\Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P} ,

donde P es el conjunto de problemas de decisión resolubles en tiempo polinomial . Entonces, para i^n ≥ 0, definimos

\Delta _{i+1}^{\mathrm {P} }:=\mathrm {P} ^{\Sigma _{i}^{\mathrm {P} }}

\Sigma _{i+1}^{\mathrm {P} }:=\mathrm {NP} ^{\Sigma _{i}^{\mathrm {P} }}

\Pi _{i+1}^{\mathrm {P} }:=\mathrm {coNP} ^{\Sigma _{i}^{\mathrm {P} }}

dónde $\mathrm {P} ^{\rm {A}}$ es el conjunto de problemas de decisión resolubles en tiempo polinomial por una máquina de Turing aumentada por un oráculo para algún problema completo en la clase A; las clases $\mathrm {NP} ^{\rm {A}}$ y $\mathrm {coNP} ^{\rm {A}}$ se definen de forma análoga. Por ejemplo, $\Sigma _{1}^{\mathrm {P} }=\mathrm {NP} ,\Pi _{1}^{\mathrm {P} }=\mathrm {coNP}$ , y $\Delta _{2}^{\mathrm {P} }=\mathrm {P^{NP}}$ es la clase de problemas que se pueden resolver en tiempo polinomial mediante una máquina de Turing determinista con un oráculo para algún problema NP-completo. ^{[ 2 ]}

Definición de fórmulas booleanas cuantificadas

Para la definición existencial/universal de la jerarquía polinómica, sea $L$ un lenguaje (es decir, un problema de decisión , un subconjunto de {0,1} ^* ), sea $p$ un polinomio y definamos

\exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},

dónde $\langle x,w\rangle \in \{0,1\}^{*}$ es una codificación estándar del par de cadenas binarias x y w como una sola cadena binaria. El lenguaje L representa un conjunto de pares ordenados de cadenas, donde la primera cadena x es un miembro de $\exists ^{p}L$ y la segunda cadena w es una "corta" ( $|w|\leq p(|x|)$ ) testigo que declara que x es miembro de $\exists ^{p}L$ . En otras palabras, $x\in \exists ^{p}L$ si y solo si existe un testigo corto w tal que $\langle x,w\rangle \in L$ . De manera similar, defina

\forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}

Nótese que las leyes de De Morgan se mantienen: $\left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}$ y $\left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}$ , donde L ^c es el complemento de L .

Sea C una clase de lenguajes. Extienda estos operadores para que funcionen en clases completas de lenguajes mediante la definición.

\exists ^{\mathrm {P} }{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}

\forall ^{\mathrm {P} }{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}

Una vez más, las leyes de De Morgan se mantienen: $\mathrm {co} \exists ^{\mathrm {P} }{\mathcal {C}}=\forall ^{\mathrm {P} }\mathrm {co} {\mathcal {C}}$ y $\mathrm {co} \forall ^{\mathrm {P} }{\mathcal {C}}=\exists ^{\mathrm {P} }\mathrm {co} {\mathcal {C}}$ , dónde $\mathrm {co} {\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}$ .

Las clases NP y co-NP se pueden definir como $\mathrm {NP} =\exists ^{\mathrm {P} }\mathrm {P}$ , y $\mathrm {coNP} =\forall ^{\mathrm {P} }\mathrm {P}$ , donde P es la clase de todos los lenguajes factiblemente decidibles (en tiempo polinomial). La jerarquía polinomial se puede definir recursivamente como

\Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P}

\Sigma _{k+1}^{\mathrm {P} }:=\exists ^{\mathrm {P} }\Pi _{k}^{\mathrm {P} }

\Pi _{k+1}^{\mathrm {P} }:=\forall ^{\mathrm {P} }\Sigma _{k}^{\mathrm {P} }

Tenga en cuenta que $\mathrm {NP} =\Sigma _{1}^{\mathrm {P} }$ , y $\mathrm {coNP} =\Pi _{1}^{\mathrm {P} }$ .

Esta definición refleja la estrecha conexión entre la jerarquía polinómica y la jerarquía aritmética , donde R y RE desempeñan funciones análogas a P y NP , respectivamente. La jerarquía analítica también se define de manera similar para proporcionar una jerarquía de subconjuntos de los números reales .

Definición de máquinas de Turing alternas

Una máquina de Turing alternante es una máquina de Turing no determinista con estados no finales divididos en estados existenciales y universales. Es eventualmente aceptable desde su configuración actual si: está en un estado existencial y puede transitar a alguna configuración eventualmente aceptable; o está en un estado universal y cada transición es a alguna configuración eventualmente aceptable; o está en un estado aceptable. ^{[ 3 ]}

Nosotros definimos $\Sigma _{k}^{\mathrm {P} }$ ser la clase de lenguajes aceptados por una máquina de Turing alternante en tiempo polinomial tal que el estado inicial es un estado existencial y cada camino que la máquina puede tomar intercambia como máximo k – 1 veces entre estados existenciales y universales. Definimos $\Pi _{k}^{\mathrm {P} }$ De manera similar, excepto que el estado inicial es un estado universal. ^{[ 4 ]}

Si omitimos el requisito de como máximo k – 1 intercambios entre los estados existencial y universal, de modo que solo requerimos que nuestra máquina de Turing alternante se ejecute en tiempo polinomial, entonces tenemos la definición de la clase AP , que es igual a PSPACE . ^{[ 5 ]}

Relaciones entre clases en la jerarquía polinómica

La unión de todas las clases en la jerarquía polinómica es la clase de complejidad PH .

Las definiciones implican las siguientes relaciones:

\Sigma _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Sigma _{i+1}^{\mathrm {P} }

\Pi _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Pi _{i+1}^{\mathrm {P} }

\Sigma _{i}^{\mathrm {P} }=\mathrm {co} \Pi _{i}^{\mathrm {P} }

A diferencia de las jerarquías aritmética y analítica, cuyas inclusiones se sabe que son propias, es una cuestión abierta si alguna de estas inclusiones es propia, aunque se cree ampliamente que todas lo son. Si alguna $\Sigma _{k}^{\mathrm {P} }=\Sigma _{k+1}^{\mathrm {P} }$ o si alguno $\Sigma _{k}^{\mathrm {P} }=\Pi _{k}^{\mathrm {P} }$ , entonces la jerarquía se derrumba al nivel k : para todo $i>k$ , $\Sigma _{i}^{\mathrm {P} }=\Sigma _{k}^{\mathrm {P} }$ . ^{[ 6 ]} En particular, tenemos las siguientes implicaciones relacionadas con problemas sin resolver:

P = NP si y solo si P = PH .^{[ 7 ]}
Si NP = co-NP entonces NP = PH . ( co-NP es $\Pi _{1}^{\mathrm {P} }$ .)

El caso en el que NP = PH también se denomina colapso de PH al segundo nivel . El caso P = NP corresponde a un colapso de PH a P.

Problema sin resolver en informática

⁠

\mathrm {P} {\overset {?}{=}}\mathrm {NP}

⁠

Más problemas sin resolver en informática

La cuestión del colapso al primer nivel se considera, en general, extremadamente difícil. La mayoría de los investigadores no creen en un colapso, ni siquiera al segundo nivel.

Relaciones con otras clases

Problema sin resolver en informática

⁠

\mathrm {PH} {\overset {?}{=}}\mathrm {PSPACE}

⁠

Más problemas sin resolver en informática

Diagrama de Hasse de clases de complejidad que incluyen P , NP , co-NP , BPP , P/poly , PH y PSPACE.

La jerarquía polinómica es un análogo (con una complejidad mucho menor) de la jerarquía exponencial y la jerarquía aritmética .

Se sabe que PH está contenido en PSPACE , pero se desconoce si ambas clases son iguales. Una reformulación útil de este problema es que PH = PSPACE si y solo si la lógica de segundo orden sobre estructuras finitas no obtiene potencia adicional al añadir un operador de cierre transitivo sobre relaciones de relaciones (es decir, sobre las variables de segundo orden). ^{[ 8 ]}

Si la jerarquía polinómica tiene algún problema completo , entonces tiene solo un número finito de niveles distintos. Dado que existen problemas PSPACE-completos , sabemos que si PSPACE = PH, entonces la jerarquía polinómica debe colapsar, ya que un problema PSPACE-completo sería un $\Sigma _{k}^{\mathrm {P} }$ -problema completo para algún k . ^{[ 9 ]}

Cada clase en la jerarquía polinómica contiene $\leq _{\rm {m}}^{\mathrm {P} }$ -problemas completos (problemas completos bajo reducciones muchos a uno en tiempo polinomial). Además, cada clase en la jerarquía polinomial es cerrada bajo $\leq _{\rm {m}}^{\mathrm {P} }$ -reducciones : lo que significa que para una clase C en la jerarquía y un lenguaje $L\in {\mathcal {C}}$ , si $A\leq _{\rm {m}}^{\mathrm {P} }L$ , entonces $A\in {\mathcal {C}}$ también. Estos dos hechos juntos implican que si $K_{i}$ es un problema completo para $\Sigma _{i}^{\mathrm {P} }$ , entonces $\Sigma _{i+1}^{\mathrm {P} }=\mathrm {NP} ^{K_{i}}$ , y $\Pi _{i+1}^{\mathrm {P} }=\mathrm {coNP} ^{K_{i}}$ . Por ejemplo, $\Sigma _{2}^{\mathrm {P} }=\mathrm {NP} ^{\mathrm {SAT} }$ En otras palabras, si un lenguaje se define a partir de algún oráculo en C , podemos asumir que se define a partir de un problema completo para C. Por lo tanto, los problemas completos actúan como "representantes" de la clase para la cual son completos.

Teorema de Sipser-Lautemann : $\mathrm {BPP} \subset \Sigma _{2}^{\mathrm {P} }\cap \Pi _{2}^{\mathrm {P} }$ .
Teorema de Kannan : $\forall k,\Sigma _{2}\not \subset \mathrm {SIZE} (n^{k})$ Es una cuestión abierta si $\Sigma _{2}\not \subset \bigcup _{k}\mathrm {SIZE} (n^{k})=\mathrm {P/poly}$ .
Teorema de Toda : $\mathrm {PH} \subset \mathrm {P} ^{\mathrm {\#P} }$ .

Existe cierta evidencia de que BQP , la clase de problemas que se pueden resolver en tiempo polinomial mediante una computadora cuántica , no está contenida en PH; sin embargo, también se cree que PH no está contenida en BQP. ^{[ 10 ]}^{[ 11 ]}

Problemas

Un ejemplo de un problema natural en $\Sigma _{2}^{\mathrm {P} }$ es minimización de circuitos : dado un número k y un circuito A que calcula una función booleana f , determinar si existe un circuito con como máximo k compuertas que calcule la misma función f . Sea C el conjunto de todos los circuitos booleanos. El lenguaje
$L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\text{ has at most }}k{\text{ gates, and }}A(x)=B(x)\right.\right\}$
es decidible en tiempo polinomial. El lenguaje
${\mathit {CM}}=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\text{there exists a circuit }}B{\text{ with at most }}k{\text{ gates }}\\{\text{ such that }}A{\text{ and }}B{\text{ compute the same function}}\end{matrix}}\right.\right\}$
es el lenguaje de minimización de circuitos. ${\mathit {CM}}\in \Sigma _{2}^{\mathrm {P} }(=\exists ^{\mathrm {P} }\forall ^{\mathrm {P} }\mathrm {P} )$ porque $L$ es decidible en tiempo polinomial y porque, dado $\langle A,k\rangle$ , $\langle A,k\rangle \in {\mathit {CM}}$ si y solo si existe un circuito $B$ tal que para todas las entradas $x$ , $\langle A,k,B,x\rangle \in L$ .
Un problema completo para $\Sigma _{k}^{\mathrm {P} }$ es la satisfacibilidad para fórmulas booleanas cuantificadas con k – 1 alternancias de cuantificadores (abreviado QBF _k o QSAT _k ). Esta es la versión del problema de satisfacibilidad booleana para $\Sigma _{k}^{\mathrm {P} }$ En este problema, se nos da una fórmula booleana f con variables particionadas en k conjuntos X ₁ , ..., X _k . Tenemos que determinar si es cierto que
$\exists X_{1}\forall X_{2}\exists X_{3}\ldots f$
Es decir, ¿existe una asignación de valores a las variables en X ₁ tal que, para todas las asignaciones de valores en X ₂ , existe una asignación de valores a las variables en X ₃ , ... f es verdadero?
La variante anterior está completa para $\Sigma _{k}^{\mathrm {P} }$ . La variante en la que el primer cuantificador es "para todos", el segundo es "existe", etc., es completa para $\Pi _{k}^{\mathrm {P} }$ . Cada lenguaje es un subconjunto del problema obtenido al eliminar la restricción de k – 1 alternancias, el problema TQBF completo de PSPACE .
En este compendio se puede encontrar una lista de problemas al estilo de Garey/Johnson que se sabe que están completos para el segundo nivel y los niveles superiores de la jerarquía polinómica .

Véase también

Referencias

Referencias generales

Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Cambridge University Press. ISBN 978-0-521-42426-4. sección 1.4, "Máquinas como cadenas y la máquina de Turing universal" y 1.7, "Demostración del teorema 1.9"
AR Meyer y LJ Stockmeyer . El problema de equivalencia para expresiones regulares con elevación al cuadrado requiere espacio exponencial. En Actas del 13.º Simposio IEEE sobre Teoría de Conmutación y Autómatas , págs. 125-129 , 1972. El artículo que introdujo la jerarquía polinómica.
LJ Stockmeyer . La jerarquía de tiempo polinomial . Theoretical Computer Science , vol. 3 , págs. 1-22 , 1976.
C. Papadimitriou . Complejidad computacional. Addison-Wesley, 1994. Capítulo 17. Jerarquía polinomial , págs. 409-438 .
Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. ISBN 0-7167-1045-5.Sección 7.2: La jerarquía polinómica, págs. 161–167.

Citas

^ Arora y Barak, 2009, págs.97
↑ Completitud en la jerarquía de tiempo polinomial: Un compendio, M. Schaefer, C. Umans
^ Arora y Barak, págs. 99-100
↑ Arora y Barak, pág. 100
↑ Arora y Barak, pág. 100
↑ Arora y Barak, 2009, Teorema 5.4
↑ Hemaspaandra, Lane (2018). "17.5 Clases de complejidad". En Rosen, Kenneth H. (ed.). Manual de matemáticas discretas y combinatorias . Matemáticas discretas y sus aplicaciones (2.ª ed.). CRC Press. pp. 1308–1314 . ISBN 9781351644051.
↑ Ferrarotti, Flavio; Van den Bussche, enero; Virtema, Jonni (2018). "Expresividad dentro de la lógica de cierre transitivo de segundo orden" . DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 . Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi : 10.4230/LIPIcs.CSL.2018.22 . S2CID 4903744 .
↑ Arora y Barak, 2009, Reivindicación 5.5
↑ Aaronson, Scott (2009). "BQP y la jerarquía polinomial". Actas del 42.º Simposio sobre Teoría de la Computación (STOC 2009) . Asociación para la Maquinaria de Computación . págs. 141–150 . arXiv : 0910.4698 . doi : 10.1145/1806689.1806711 . ECCC TR09-104 .
↑ Hartnett, Kevin (21 de junio de 2018). "Finalmente, un problema que solo las computadoras cuánticas podrán resolver" . Quanta Magazine .

[1] Arora y Barak, 2009, págs.97

[2] Completitud en la jerarquía de tiempo polinomial: Un compendio, M. Schaefer, C. Umans

[3] Arora y Barak, págs. 99-100

[4] Arora y Barak, pág. 100

[5] Arora y Barak, pág. 100

[6] Arora y Barak, 2009, Teorema 5.4

[7] Hemaspaandra, Lane (2018). "17.5 Clases de complejidad". En Rosen, Kenneth H. (ed.). Manual de matemáticas discretas y combinatorias . Matemáticas discretas y sus aplicaciones (2.ª ed.). CRC Press. pp. 1308–1314 . ISBN 9781351644051.

[8] Ferrarotti, Flavio; Van den Bussche, enero; Virtema, Jonni (2018). "Expresividad dentro de la lógica de cierre transitivo de segundo orden" . DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 . Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi : 10.4230/LIPIcs.CSL.2018.22 . S2CID 4903744 .

[9] Arora y Barak, 2009, Reivindicación 5.5

[10] Aaronson, Scott (2009). "BQP y la jerarquía polinomial". Actas del 42.º Simposio sobre Teoría de la Computación (STOC 2009) . Asociación para la Maquinaria de Computación . págs. 141–150 . arXiv : 0910.4698 . doi : 10.1145/1806689.1806711 . ECCC TR09-104 .

[11] Hartnett, Kevin (21 de junio de 2018). "Finalmente, un problema que solo las computadoras cuánticas podrán resolver" . Quanta Magazine .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]