¿Problema de interpretación simple con respecto a la jerarquía polinómica?

Entonces significa problemas en los que tenemos pequeños testigos verificables para instancias de y para pequeños testigos verificables para instancias de . ¿Cómo funciona esto para$NP$$YES$$coNP$$NO$

1. $P^{NP}$

2. $NP^{NP}$

3. $coNP^{NP}$

4. ¿y así?

Existe una interpretación lógica de los diversos niveles de la jerarquía polinómica, que amplía la caracterización del testigo de $\mathsf{NP}$ y $\mathsf{coNP}$.

Un idioma $L$ es en $\Sigma_k^P$ si hay un predicado polytime $f$ y un polinomio $\ell$ tal que

• $\exists |y| \le \ell(|x|)$ significa que existe un número $y$ cuya longitud es como máximo $\ell(|x|)$ tal que ...
• $\forall |y| \le \ell(|x|)$ significa que para todos $y$ cuya longitud es como máximo $\ell(|x|)$, lo siguiente se cumple ...
• $Q$ es $\exists$ Si $k$ es extraño y $\forall$ Si $k$ incluso.

Similar, $L$ es en $\Pi_k^P$ si se puede escribir de manera similar, solo comenzando con $\forall$.

Como ejemplo, $\mathsf{NP}^{\mathsf{NP}}$ es $\Sigma_2^P$y consta de todos los idiomas de modo que

Tu tercer ejemplo es $\mathsf{P}^{\mathsf{NP}}$, cual es $\Delta_2^P$. No estoy seguro de cuál es la caracterización lógica.

Decir $\mathsf{NP}$contiene problemas con "pequeños testigos verificables" es conceptualmente inexacto en el mejor de los casos. Los testigos solo están polinómicamente delimitados porque queremos que el verificador sea eficiente (es decir, que se ejecute en tiempo polinómico). En tal contexto, solo un prefijo polinomialmente largo de cualquier testigo puede ser relevante, de ahí que insistimos en testigos polinomialmente largos. Además, "pequeño" significa potencialmente constante o logarítmico; esos no se usan, por supuesto, porque pueden ser forzados por los algoritmos de tiempo polinómico (y solo nos dan problemas en$\mathsf{P}$)

La forma en que el sistema de prueba noción de $\mathsf{NP}$Generalizar para producir la jerarquía polinómica es muy similar al punto de vista lógico que Yuval Filmus describe en su respuesta. Permítanme presentarles la visión menos técnica detrás de esto.

Consideramos los juegos de dos partes que se basan en QBF. Una instancia (o el "tablero" si quieres imaginarlo como un juego de tablero como el ajedrez o las damas) de tal juego es una fórmula$\varphi(x_1, y_1, \ldots, x_m, y_m)$y los dos jugadores dicen $A$ y $B$, se turnan para elegir valores para $x_i$ y $y_i$, respectivamente. Cada una de esas elecciones constituye un movimiento . Cuando no quedan más valores, se evalúa la fórmula (es decir, la posición final del juego);$A$ gana si es verdad, y $B$ gana si es falso.

Este juego modela cuantificadores existenciales y universales de la siguiente manera: si la fórmula es un verdadero QBF, entonces $A$ (que desempeña el papel de cuantificadores existenciales) siempre tendrá una estrategia ganadora y podrá elegir una serie de $x_1, \ldots, x_m$ que causa $\varphi$ ser cierto independientemente de los valores $y_1, \ldots, y_m$ recogido por $B$(que desempeña el papel de cuantificadores universales). Las instancias "sí" son aquellas en las que el QBF es verdadero, es decir,$A$ siempre tiene una estrategia ganadora, independientemente de cómo $B$ obras de teatro.

$\Sigma_i$ y $\Pi_i$ luego corresponden a juegos que duran $i$ se mueve y en el que $A$ y $B$, respectivamente, llegar primero. En realidad, incluso obtienes$\textsf{PSPACE}$ y el $\textsf{PH} \subseteq \textsf{PSPACE}$ inclusión como un bono ya que corresponde a la clase de juegos que continúan por un número arbitrario (aunque predeterminado) de movimientos.

Tenga en cuenta también que $\Sigma_1 = \mathsf{NP}$ y $\Pi_1 = \mathsf{coNP}$ son casos bastante degenerados de estos juegos porque $B$ y $A$, respectivamente, ¡no tengas la oportunidad de moverte en absoluto! Por ejemplo, para las instancias "yes" de$\Pi_1 = \mathsf{coNP}$, $A$ llega a ganar simplemente al no hacer nada (ya que una instancia de "sí" es una tautología y es verdadera independientemente de lo que $B$ elige).

También hay una versión más generalizada de lo anterior que se basa en juegos genéricos (y no en QBF específicamente). Puede encontrarlo, por ejemplo, en la sección 5.4 "PSPACE y juegos" de "Complejidad computacional: una perspectiva conceptual" de Goldreich ( aquí hay un enlace gratuito a la versión borrador; consulte las páginas 174 y 118-121) .

$\mathsf{P}^{\mathsf{NP}}$ es el cierre de $\mathsf{NP}$bajo tiempo polinómico reducciones de Turing (= reducciones de cocción). Por lo tanto, está cerrado bajo las reducciones de Cook, por lo que tenemos$\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{P}^{\mathsf{NP}}}$. De hecho, para cualquier oráculo$\mathsf{A}$, definimos $\mathsf{P}^{\mathsf{A}}$ como el cierre de $\mathsf{A}$ bajo las reducciones de Cook, y siempre tenemos $\mathsf{P}^{\mathsf{A}}=\mathsf{P}^{\mathsf{P}^{\mathsf{A}}}$ y $\mathsf{NP}^{\mathsf{A}}=\mathsf{NP}^{\mathsf{P}^{\mathsf{A}}}$. también $\mathsf{coNP}^{\mathsf{A}}=\mathsf{coNP}^{\mathsf{P}^{\mathsf{A}}}$ y $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{coNP}}$. Pero las reducciones de Cook se sienten poco naturales para los problemas de decisión.

Tenga en cuenta que $\mathsf{P}$ es una clase de función en disguide, y que $\mathsf{P}^{\mathsf{NP}}$También es una clase de función disfrazada. Vamos a escribir$\mathsf{PF}$ para la clase de funciones parciales computables de tiempo polinomial, es decir, la clase de función correspondiente a $\mathsf{P}$y $\mathsf{PF}^{\mathsf{NP}}$ para la clase de función correspondiente a $\mathsf{P}^{\mathsf{NP}}$. La inclusión de las funciones parciales permite utilizar la notación establecida (utilizada en la taxonomía A de las clases de funciones complejas por A. Selman, 1994) que evita el choque de nombres con la clase no relacionada$\mathsf{FP}$.

La reducción de cocción se siente más natural para las clases funcionales. Probablemente haya encontrado una reducción de Cook (e implícitamente también la clase$\mathsf{PF}^{\mathsf{NP}}$) en el punto en el que su libro de texto o profesor explicaron por qué está bien ver solo los problemas de decisión. Típicamente, algo así como un algoritmo (de$\mathsf{PF}^{\mathsf{NP}}$) para calcular la última asignación satisfactoria lexicográfica de una instancia SAT determinada se describe. Primero se le pregunta al oráculo si hay alguna asignación satisfactoria, y luego determina los valores de las variables (binarias)$x_k$ preguntando sucesivamente al oráculo si hay una tarea satisfactoria donde $x_1,\dots,x_{k-1}$ se establecen en los valores ya determinados y $x_k$ se establece en $1$. Si es así, entonces uno establece$x_k$ a $1$, de lo contrario uno establece $x_k$ a $0$. (Tenga en cuenta que esta es una función parcial, ya que la función no está definida en caso de que no haya una asignación satisfactoria).

Permítanme tratar de decir algunas palabras sobre el comentario de Yuval Filmus:

Tu tercer ejemplo es $\mathsf{P}^{\mathsf{NP}}$, cual es $\Delta_2^P$. No estoy seguro de cuál es la caracterización lógica.

Hay dos dificultades que superar: (1) la caracterización de una clase de función tiene una sensación diferente que la caracterización lógica de una clase de decisión, y (2) al menos para $\mathsf{P}^{\mathsf{A}}$tenemos que modelar el carácter determinista de las consultas al oráculo$\mathsf{A}$.

Si miramos la clase $\mathsf{UPF}$ de funciones parciales correspondientes a la clase $\mathsf{UP}$ de los problemas de decisión primero, luego podemos ignorar (2) por un momento: una función parcial $pf$ es en $\mathsf{UPF}^{\Sigma_k^P}$ si hay una función parcial polytime $p$, un predicado polytime $f$ y un polinomio $\ell$ tal que $pf(x)=p(x,z)$ dónde

• $\exists |y| \le \ell(|x|)$ significa que existe un número $y$ cuya longitud es como máximo $\ell(|x|)$ tal que ...
• $\forall |y| \le \ell(|x|)$ significa que para todos $y$ cuya longitud es como máximo $\ell(|x|)$, lo siguiente se cumple ...
• $Q$ es $\exists$ Si $k$ es extraño y $\forall$ Si $k$ incluso.

Se podría tratar de superar (2) introduciendo los operadores $\operatorname{BIT}(z,i):=z[i]$ y $\operatorname{TRUNC}(z,i):=z\left|_{[1,i)}\right.$. Pero todavía se pondría feo, y uno puede discutir si esto realmente constituiría una caracterización lógica.