Jerarquía polinómica

Concepto de informática

En la teoría de la complejidad computacional , la jerarquía polinómica (a veces llamada jerarquía de tiempo polinómico ) 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 se puede definir utilizando máquinas oráculo o máquinas de Turing alternas . Es una contraparte limitada por recursos 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 tienen problemas completos (con respecto a las reducciones de tiempo polinomial ) que preguntan si las fórmulas booleanas cuantificadas son válidas 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 polinomial.

Definición de Oracle

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

${\displaystyle \Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},}$

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

${\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}}$

${\displaystyle \Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}}$

${\displaystyle \Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Sigma _{i}^{\mathsf {P}}}}$

donde 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 y se definen de manera análoga. Por ejemplo, , y es la clase de problemas resolubles en tiempo polinomial por una máquina de Turing determinista con un oráculo para algún problema NP-completo. ^[2] ${\displaystyle {\mathsf {P}}^{\rm {A}}}$ ${\displaystyle {\mathsf {NP}}^{\rm {A}}}$ ${\displaystyle {\mathsf {coNP}}^{\rm {A}}}$ ${\displaystyle \Sigma _{1}^{\mathsf {P}}={\mathsf {NP}},\Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}}$ ${\displaystyle \Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}}$

Definición de fórmulas booleanas cuantificadas

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

${\displaystyle \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\},}$

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

${\displaystyle \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 cumplen: y , donde L ^c es el complemento de L . ${\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}}$ ${\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}$

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

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

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

Nuevamente, las leyes de De Morgan se cumplen: y , donde . ${\displaystyle {\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}$ ${\displaystyle {\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}$ ${\displaystyle {\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}$

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

${\displaystyle \Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}}$

${\displaystyle \Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}}$

${\displaystyle \Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}}$

Téngase en cuenta que , y . ${\displaystyle {\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}}$ ${\displaystyle {\mathsf {coNP}}=\Pi _{1}^{\mathsf {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 papeles análogos a P y NP , respectivamente. La jerarquía analítica también se define de manera similar para dar una jerarquía de subconjuntos de los números reales .

Definición de máquinas de Turing alternadas

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 realizar la transición hacia alguna configuración eventualmente aceptable; o, está en un estado universal y cada transición es hacia alguna configuración eventualmente aceptable; o, está en un estado aceptable. ^[3]

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

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 alternada funcione 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

Diagrama conmutativo equivalente a la jerarquía de tiempo polinomial. Las flechas indican inclusión.

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

Las definiciones implican las relaciones:

${\displaystyle \Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}}$

${\displaystyle \Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}}$

${\displaystyle \Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}}$

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

• P = NP si y sólo si P = PH . ^[7]
• Si NP = co-NP entonces NP = PH . ( co-NP es .) ${\displaystyle \Pi _{1}^{\mathsf {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 :

⁠ ⁠ ${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {NP}}}$

(más problemas sin resolver en informática)

En general, se considera que la cuestión del colapso al primer nivel es 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 :

⁠ ⁠ ${\displaystyle {\mathsf {PH}}{\overset {?}{=}}{\mathsf {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 polinomial es un análogo (de mucha menor complejidad) de la jerarquía exponencial y de la jerarquía aritmética .

Se sabe que PH está contenido dentro de PSPACE , pero no se sabe si las dos 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 de la adición de un operador de clausura transitiva 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 hay 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 problema -completo para algún k . ^[9] ${\displaystyle \Sigma _{k}^{\mathsf {P}}}$

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

El teorema de Sipser-Lautemann establece que la clase BPP está contenida en el segundo nivel de la jerarquía polinomial.

El teorema de Kannan establece que para cualquier k , no está contenido en TAMAÑO (n ^k ). ${\displaystyle \Sigma _{2}}$

El teorema de Toda establece que la jerarquía polinomial está contenida en P ^#P .

Problemas

• Un ejemplo de un problema natural es la minimización de circuitos : dado un número k y un circuito A que calcula una función booleana f , determine si hay un circuito con como máximo k puertas que calcule la misma función f . Sea C el conjunto de todos los circuitos booleanos. El lenguaje ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$

  ${\displaystyle 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

  ${\displaystyle {\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. porque L es decidible en tiempo polinomial y porque, dado , si y solo si existe un circuito B tal que para todas las entradas x , . ${\displaystyle {\mathit {CM}}\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})}$ ${\displaystyle \langle A,k\rangle }$ ${\displaystyle \langle A,k\rangle \in {\mathit {CM}}}$ ${\displaystyle \langle A,k,B,x\rangle \in L}$
• Un problema completo para 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 . En este problema, se nos da una fórmula booleana f con variables divididas en k conjuntos X ₁ , ..., X _k . Tenemos que determinar si es cierto que ${\displaystyle \Sigma _{k}^{\mathsf {P}}}$ ${\displaystyle \Sigma _{k}^{\mathsf {P}}}$

  ${\displaystyle \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 ₂ , exista una asignación de valores a las variables en X ₃ , ... f es verdadera? La variante anterior es completa para . La variante en la que el primer cuantificador es "para todos", el segundo es "existe", etc., es completa para . Cada lenguaje es un subconjunto del problema obtenido al eliminar la restricción de k – 1 alternancias, el problema PSPACE - completo TQBF . ${\displaystyle \Sigma _{k}^{\mathsf {P}}}$ ${\displaystyle \Pi _{k}^{\mathsf {P}}}$
• En este Compendio se puede encontrar una lista al estilo Garey/Johnson de problemas que se sabe que están completos para el segundo nivel y niveles superiores de la jerarquía polinomial.

Véase también

• TIEMPO EXPERIMENTAL
• Jerarquía exponencial
• Jerarquía aritmética

Referencias

Referencias generales

1. 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 cuerdas y la máquina universal de Turing" y 1.7, "Demostración del teorema 1.9"
2. 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 conmutación y teoría de autómatas , págs. 125-129, 1972. El artículo que introdujo la jerarquía polinómica.
3. LJ Stockmeyer . La jerarquía de tiempo polinomial. Theoretical Computer Science , vol. 3, págs. 1–22, 1976.
4. C. Papadimitriou . Computational Complexity. Addison-Wesley, 1994. Capítulo 17. Jerarquía polinomial , págs. 409–438.
5. Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. ISBN 0-7167-1045-5.Sección 7.2: La jerarquía polinomial, págs. 161–167.

Citas

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áginas 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. págs. 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