Clase de pH

Clase de complejidad PH (de la jerarquía de polinomios en inglés ): la unión de todas las clases de complejidad de la jerarquía de polinomios :

{\mbox{PH}}=\bigcup_{k\in \mathbb {N} }\left(\Sigma_{k}^{p}\cup \Pi_{k}^{p}\right)= \bigcup _{k\in \mathbb {N} }\Sigma _{k}^{p}=\bigcup _{k\in \mathbb {N} }\Pi _{k}^{p}

Así, un predicado pertenece a la clase PH si existe k tal que el predicado pertenece a la clase o . También se dice que la lengua reconocida por tal predicado (es decir, el conjunto de todas las palabras para las que el predicado devuelve 1) pertenece a la clase PH. $\Sigma _{k}^{p}$ $\Pi _{k}^{p}$

Definiciones equivalentes

Caracterización lógica

La clase de lenguajes PH es exactamente igual a la clase de lenguajes expresables por lógica de segundo orden .

Caracterización del juego

Llamamos a la siguiente estructura un juego finito . Hay un árbol cuyos vértices están etiquetados con los nombres de dos jugadores A y B (todos los vértices del mismo nivel están etiquetados con el mismo nombre, los movimientos se alternan), y los bordes corresponden a los movimientos de los jugadores. Deje que se dé alguna palabra inicial x : la configuración inicial del juego. Entonces, el número de niveles en el árbol (es decir, el número de movimientos) es igual a alguna función f de longitud x , y cada borde se etiqueta con una palabra de longitud g de longitud x (la jugada del jugador es la palabra que etiqueta el borde). Hay un predicado de la configuración inicial y la secuencia de movimientos de los jugadores, que determina quién ganó (si es igual a 1, entonces ganó el primer jugador). Dado que el juego es finito, el primer jugador o el segundo siempre tienen una estrategia ganadora. Llamemos a un juego que reconoce el idioma L si por cada palabra x de L el jugador A tiene una estrategia ganadora. $R(x,w_{1}w_{2}w_{3}\puntos)$

La clase PH es la clase de todos los idiomas reconocidos por los juegos, de modo que f es una constante (es decir, el número de movimientos en el juego es fijo y no depende de la longitud de la palabra de entrada) y g es un polinomio de longitud x (así, de cada vértice del árbol, excepto el último, se procede a lo largo de las aristas, donde está este polinomio). $2^{p(n)}$ $p(n)$

Cierre

A diferencia de las clases de la jerarquía polinomial que componen la clase PH, se sabe con certeza que PH es cerrado bajo la intersección, unión y complemento de lenguajes. Esto quiere decir que si los idiomas y pertenecen a PH, entonces los idiomas y pertenecen a PH. $L_{1}$ $L_{2}$ $L_{1}\cap L_{2}$ $L_{1}\taza L_{2}$ $L_{1}^{c}$

Para probarlo, basta con presentar juegos que reconozcan estas combinaciones de lenguajes, si es que existen juegos que reconozcan y . Para el complemento, transfiramos el derecho del primer movimiento a otro jugador y tomemos . Para intersectar, tomamos dos juegos reconociendo y , tal que el número de movimientos en ellos es el mismo, y el segundo no lo inicia el jugador que hace el último movimiento en el primero. Después de eso, agregamos el segundo juego a cada vértice final del primer juego, y tomamos como predicado de pago , donde y es la división de toda la secuencia de movimientos en dos partes: la parte correspondiente al primer juego y la parte correspondiente al segundo Para unir, tomamos juegos que reconocen y , con el mismo número de movimientos y el mismo primer jugador. Vamos a crear un nuevo vértice correspondiente a otro jugador y adjuntarle un árbol del primer juego (escribimos la palabra 00...0 sobre este borde) y los bordes restantes del segundo juego. Denotamos la primera palabra del juego por z , y el resto de la secuencia de palabras por , y tomamos como predicado de pago . $L_{1}$ $L_{2}$ $\neg R_{1}$ $L_{1}$ $L_{2}$ $R_{1}(x,\,\omega _{1})\cuña R_{2}(x,\,\omega _{2})$ $\omega_{1}$ $\omega _{2}$ $L_{1}$ $L_{2}$ $2^{{p(n)}}-1$ $\omega$ $(z=00\dots 0\wedge R_{1}(x,\omega ))\vee (z\neq 00\dots 0\wedge R_{2}(x,\omega ))$

Relaciones con otras clases

Por definición, la clase PH incluye todas las clases de la jerarquía polinomial, incluidas P y NP . Además, contiene clases probabilísticas, como la clase BPP (porque BPP está contenido en la clase ). La clase PH en sí está incluida en la clase PSPACE y la clase P PP (una clase de problemas que se resuelven en tiempo polinomial en una máquina de Turing con acceso al oráculo de la clase PP ). $\Sigma _{2}^{p}$

Temas abiertos

Se establece que P = NP si y sólo si P = PH. Esta afirmación puede facilitar la demostración de que P ≠ NP (si es así), ya que solo sería necesario separar P de una clase más general que NP.

Clases de complejidad de algoritmos
Considerado ligero	DLOGTIME CA 0 ACC 0 TC0 [ es L SL RL Países Bajos CAROLINA DEL NORTE SC CC PAGS P-completa ZPP PR BPP BQP EQP APX
Se supone que es difícil	UP notario público NP completo co-NP co-NP-completo AM MA QMA PH ⊕P PÁGINAS #PAGS #P- IP ESPACIO P PSPACE-completo
Considerado difícil	EXPTIME NEXPTIME EXPESPACIO 2-EXPTIM PRIMARIA R PR RE RE-completar Co-RE Co-RE-completo TODOS