Problema de interpretação simples em relação à hierarquia polinomial?

Portanto, representa problemas nos quais temos pequenas testemunhas verificáveis ​​para instâncias e para pequenas testemunhas verificáveis ​​para instâncias. Como isso funciona para$NP$$YES$$coNP$$NO$

1. $P^{NP}$

2. $NP^{NP}$

3. $coNP^{NP}$

4. e assim por diante?

Há uma interpretação lógica dos vários níveis da hierarquia polinomial, que estende a caracterização de testemunha de e .$\mathsf{NP}$$\mathsf{coNP}$

Um idioma está em se houver um predicado de politempo e um polinômio tal que Aqui:$L$$\Sigma_k^P$$f$$\ell$

• $\exists |y| \le \ell(|x|)$ significa que existe um número cujo comprimento é no máximo tal que ...$y$$\ell(|x|)$
• $\forall |y| \le \ell(|x|)$ significa que, para todo cujo comprimento seja no máximo , o seguinte é válido ...$y$$\ell(|x|)$
• $Q$ é se for ímpar e se for par.$\exists$$k$$\forall$$k$

Da mesma forma, está em se puder ser escrito de maneira semelhante, começando apenas com .$L$$\Pi_k^P$$\forall$

Como exemplo, é e consiste em todos os idiomas, de modo que Como outro exemplo, é .$\mathsf{NP}^{\mathsf{NP}}$$\Sigma_2^P$

Seu terceiro exemplo é , que é . Não sei qual é a caracterização lógica.$\mathsf{P}^{\mathsf{NP}}$$\Delta_2^P$

Dizer $\mathsf{NP}$contém problemas com "pequenas testemunhas verificáveis" é conceitualmente imprecisa. As testemunhas são limitadas apenas polinomialmente porque queremos que o verificador seja eficiente (ou seja, executado em tempo polinomial). Nesse cenário, apenas um prefixo polinomialmente longo de qualquer testemunha pode ser relevante; daí, por que insistimos em testemunhas polinomialmente longas. Além disso, "pequeno" significa potencialmente constante ou logarítmico; essas não são usadas, é claro, porque podem ser forçadas de maneira bruta por algoritmos de tempo polinomial (e apenas nos dão problemas em$\mathsf{P}$)

A maneira como a noção de sistema de prova de $\mathsf{NP}$generaliza para produzir a hierarquia polinomial é muito parecido com o ponto de vista lógico que Yuval Filmus descreve em sua resposta. Deixe-me apresentar a visão menos técnica por trás disso.

Consideramos jogos de duas partes baseados em QBFs. Uma instância (ou o "tabuleiro", se você quiser imaginá-lo como um jogo de tabuleiro como xadrez ou damas) de um jogo desse tipo é uma fórmula$\varphi(x_1, y_1, \ldots, x_m, y_m)$e os dois jogadores dizem $A$ e $B$, revezando-se escolhendo valores para $x_i$ e $y_i$, respectivamente. Cada uma dessas escolhas constitui um movimento . Quando não restam mais valores, a fórmula (ou seja, a posição final do jogo) é avaliada;$A$ vence se for verdade e $B$ ganha se for falso.

Este jogo modela quantificadores existenciais e universais da seguinte maneira: Se a fórmula for um verdadeiro QBF, então $A$ (que desempenha o papel de quantificadores existenciais) sempre terá uma estratégia vencedora e poderá escolher uma série de $x_1, \ldots, x_m$ que causa $\varphi$ para ser verdade, independentemente dos valores $y_1, \ldots, y_m$ escolhido por $B$(que desempenha o papel de quantificadores universais). As instâncias "yes" são aquelas nas quais o QBF é verdadeiro, ou seja,$A$ sempre tem uma estratégia vencedora, independentemente de como $B$ tocam.

$\Sigma_i$ e $\Pi_i$ correspondem então a jogos que duram $i$ movimentos e em que $A$ e $B$, respectivamente, comece primeiro. Na verdade, você ainda recebe$\textsf{PSPACE}$ e a $\textsf{PH} \subseteq \textsf{PSPACE}$ inclusão como bônus, uma vez que corresponde à classe de jogos que se prolongam por um número arbitrário (embora predeterminado) de jogadas.

Note também que $\Sigma_1 = \mathsf{NP}$ e $\Pi_1 = \mathsf{coNP}$ são casos bastante degenerados desses jogos porque $B$ e $A$, respectivamente, não têm a chance de se mover! Por exemplo, para as instâncias "yes" de$\Pi_1 = \mathsf{coNP}$, $A$ consegue vencer simplesmente sem fazer nada (já que uma instância "yes" é uma tautologia e é verdadeira independentemente do que $B$ escolhe).

Há também uma versão mais generalizada do anterior, baseada em jogos genéricos (e não especificamente em QBFs). Você pode encontrá-lo, por exemplo, na seção 5.4 "PSPACE e jogos" de "Complexidade computacional: uma perspectiva conceitual" de Goldreich ( aqui está um link gratuito para a versão preliminar; consulte a página 174 e as páginas 118–121) .

$\mathsf{P}^{\mathsf{NP}}$ é o fechamento de $\mathsf{NP}$sob tempo polinomial Reduções de Turing (= Reduções de Cook). Portanto, está fechado nas reduções de Cook, para que tenhamos$\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{P}^{\mathsf{NP}}}$. De fato, para qualquer oráculo$\mathsf{A}$, definimos $\mathsf{P}^{\mathsf{A}}$ como o fechamento de $\mathsf{A}$ nas reduções de Cook, e sempre temos $\mathsf{P}^{\mathsf{A}}=\mathsf{P}^{\mathsf{P}^{\mathsf{A}}}$ e $\mathsf{NP}^{\mathsf{A}}=\mathsf{NP}^{\mathsf{P}^{\mathsf{A}}}$. Além disso $\mathsf{coNP}^{\mathsf{A}}=\mathsf{coNP}^{\mathsf{P}^{\mathsf{A}}}$ e $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{coNP}}$. Mas as reduções de Cook parecem um pouco antinaturais para problemas de decisão.

Observe que $\mathsf{P}$ é uma classe de função disfarçada e que $\mathsf{P}^{\mathsf{NP}}$também é uma classe de função disfarçada. Vamos escrever$\mathsf{PF}$ para a classe de funções parciais computáveis ​​em tempo polinomial, ou seja, a classe de função correspondente a $\mathsf{P}$e $\mathsf{PF}^{\mathsf{NP}}$ para a classe de função correspondente a $\mathsf{P}^{\mathsf{NP}}$. A inclusão de funções parciais permite usar a notação estabelecida (usada em A. taxman da complexidade classes de funções de A. Selman, 1994) que evita o conflito de nomes com a classe não relacionada$\mathsf{FP}$.

A redução de cozimento parece mais natural para as classes de funções. Você provavelmente encontrou uma redução de Cook (e implicitamente também a classe$\mathsf{PF}^{\mathsf{NP}}$) no ponto em que seu livro ou professor explicou por que não há problema em analisar apenas os problemas de decisão. Normalmente, algo como um algoritmo (de$\mathsf{PF}^{\mathsf{NP}}$) para calcular a última atribuição lexicograficamente satisfatória de uma determinada instância SAT é descrita. Primeiro, pergunta-se ao oráculo se existe alguma atribuição satisfatória e depois determina os valores das variáveis ​​(binárias)$x_k$ perguntando sucessivamente ao oráculo se existe uma tarefa satisfatória onde $x_1,\dots,x_{k-1}$ são definidos com os valores já determinados e $x_k$ está configurado para $1$. Se sim, então um define$x_k$ para $1$, caso contrário, um define $x_k$ para $0$. (Observe que essa é uma função parcial, pois a função é indefinida caso não haja uma atribuição satisfatória.)

Deixe-me tentar dizer algumas palavras sobre a observação de Yuval Filmus:

Seu terceiro exemplo é $\mathsf{P}^{\mathsf{NP}}$, qual é $\Delta_2^P$. Não sei qual é a caracterização lógica.

Há duas dificuldades a serem superadas: (1) a caracterização de uma classe de função tem uma sensação diferente da caracterização lógica de uma classe de decisão e (2) pelo menos para $\mathsf{P}^{\mathsf{A}}$temos que modelar o caráter determinístico das consultas para o oráculo$\mathsf{A}$.

Se olharmos para a classe $\mathsf{UPF}$ de funções parciais correspondentes à classe $\mathsf{UP}$ problemas de decisão primeiro, então podemos ignorar (2) por um momento: uma função parcial $pf$ é em $\mathsf{UPF}^{\Sigma_k^P}$ se houver uma função parcial polytime $p$, um predicado polytime $f$ e um polinômio $\ell$ de tal modo que $pf(x)=p(x,z)$ Onde

• $\exists |y| \le \ell(|x|)$ significa que existe um número $y$ cujo comprimento é no máximo $\ell(|x|)$ de tal modo que ...
• $\forall |y| \le \ell(|x|)$ significa que para todos $y$ cujo comprimento é no máximo $\ell(|x|)$, o seguinte contém ...
• $Q$ é $\exists$ E se $k$ é estranho e $\forall$ E se $k$ é par.

Pode-se tentar superar (2) introduzindo os operadores $\operatorname{BIT}(z,i):=z[i]$ e $\operatorname{TRUNC}(z,i):=z\left|_{[1,i)}\right.$. Mas ainda assim seria feio, e pode-se argumentar se isso realmente constituiria uma caracterização lógica.