Jerarquía polinomial

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 de la jerarquía está contenida en PSPACE . La jerarquía se puede definir utilizando máquinas Oracle o máquinas de Turing alternas . Es una contraparte limitada en 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 se cumplen, para fórmulas con restricciones en el orden de los cuantificadores. Se sabe que la igualdad entre clases del mismo nivel o 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 oráculo

Para la definición de Oracle 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 polinómico . Entonces para i ≥ 0 definir

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

¿Dónde está el conjunto de problemas de decisión que pueden resolverse en tiempo polinomial mediante una máquina de Turing aumentada por un oráculo para algún problema completo de clase A? las clases y se definen de manera análoga. Por ejemplo, y es la clase de problemas que pueden resolverse en tiempo polinómico mediante una máquina determinista de Turing 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 polinómica, 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 hay alguna 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 miembro de , y la segunda cadena w es un testigo "corto" ( ) que testifica que x es miembro de . En otras palabras, si y sólo si existe un testigo breve 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\}}$

Tenga en cuenta que se cumplen las leyes de De Morgan : 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. Amplíe estos operadores para que funcionen en clases completas de idiomas según 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, se cumplen las leyes de De Morgan: 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 decidibles (en tiempo polinomial). La jerarquía polinómica 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}}}$

Tenga 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 alternas

Una máquina de Turing alterna es una máquina de Turing no determinista con estados no finales divididos en estados existenciales y universales. Eventualmente aceptará su configuración actual si: está en un estado existencial y puede realizar la transición a alguna configuración eventualmente aceptante; o está en un estado universal y cada transición es hacia alguna configuración que finalmente se acepta; o está en un estado de aceptación. ^[3]

Definimos como la clase de lenguajes aceptados por una máquina de Turing alternante en tiempo polinómico, de modo que el estado inicial es un estado existencial y cada camino que la máquina puede tomar se intercambia como máximo k – 1 veces entre estados existencial y universal. 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 alterna funcione en tiempo polinómico, 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 temporal polinomial. Las flechas denotan inclusión.

La unión de todas las clases en la jerarquía polinómica 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ética y analítica, cuyas inclusiones se sabe que son apropiadas, queda abierta la cuestión de si alguna de estas inclusiones es apropiada, aunque se cree ampliamente que todas lo son. Si hay alguno , o si hay alguno , entonces la jerarquía colapsa al nivel k : para todos ,. ^[6] En particular, tenemos las siguientes implicaciones que involucran problemas no resueltos: ${\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 del PH al segundo nivel . El caso P = NP corresponde a un colapso de PH a P.

Problema no resuelto en informática :

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

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

Generalmente se piensa que la cuestión del colapso hasta el 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 no resuelto 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 polinómica es análoga (con una complejidad mucho menor) a la jerarquía exponencial y a la jerarquía aritmética .

Se sabe que PH está contenido en PSPACE , pero no se sabe si las dos clases son iguales. Una reformulación útil de este problema es que PH = PSPACE si y sólo si la lógica de segundo orden sobre estructuras finitas no obtiene poder adicional al agregar un operador de cierre transitivo sobre relaciones de relaciones (es decir, sobre las variables de segundo orden). ^[8]

Si la jerarquía polinomial tiene problemas completos , entonces solo tiene un número finito de niveles distintos. Dado que hay problemas de PSPACE completo , sabemos que si PSPACE = PH, entonces la jerarquía polinomial debe colapsar, ya que un problema de PSPACE completo sería un problema completo para algunos k . ^[9] ${\displaystyle \Sigma _{k}^{\mathsf {P}}}$

Cada clase en la jerarquía polinomial contiene problemas completos (problemas completos bajo reducciones de muchos uno en tiempo polinomial). Además, cada clase en la jerarquía polinómica tiene subreducciones cerradas : lo que significa que para una clase C en la jerarquía y un idioma , 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 está definido en base a un problema completo para C. Por 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 polinómica.

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 polinómica 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 calcula la misma función f . Sea C el conjunto de todos los circuitos booleanos. El idioma ${\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 idioma

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

Ver también

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

Referencias

Referencias generales

1. Arora, Sanjeev; Barac, Booz (2009). Teoría de la complejidad: un enfoque moderno. Prensa de la Universidad de Cambridge. 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 de expresiones regulares con elevación al cuadrado requiere espacio exponencial. En Actas del 13º Simposio IEEE sobre Teoría de Conmutaciones y Autómatas , págs. 125-129, 1972. El artículo que introdujo la jerarquía polinómica.
3. LJ Stockmeyer . La jerarquía del tiempo polinomial. Informática teórica , vol.3, págs. 1-22, 1976.
4. C. Papadimitriou . Complejidad computacional. Addison-Wesley, 1994. Capítulo 17. Jerarquía polinómica , 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 integridad NP . WH Freeman. ISBN 0-7167-1045-5.Sección 7.2: La jerarquía polinómica, 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ágs.100
5. Arora y Barak, págs.100
6. Arora y Barak, 2009, Teorema 5.4
7. Hemaspaandra, carril (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.). Prensa CRC. 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, afirmación 5.5