Faz

É com acesso oráculo para N P maior do que apenas N P ? Pelo que entendi N P N P é apenas uma máquina de turing que pode fazer consultas a outra máquina N P , se sim, então N P pode simular N P N P ? Há algo de errado com esse argumento?$NP$$NP$$NP$$NP^ {NP}$$NP$$NP$$NP^{NP}$

Para reformular meus comentários como resposta e expandir um pouco:

Não sabemos se NP ^NP  =  NP - é um problema notoriamente aberto na teoria da complexidade, embora, como em P versus NP , suspeitemos que eles não sejam iguais. Uma das razões pelas quais não sabemos como simular um oráculo NP com uma máquina NP é que não sabemos como a máquina NP pode detectar "não" instâncias de problemas enviados ao oráculo.

A classe NP ^NP também é conhecido como , e é uma das classes no segundo nível da hierarquia polinomial . As outras classes no segundo nível são Δ P $\Sigma_2^P$ (Todas essas classes seriam as mesmas seusássemosumoraclecoNP; a única diferença é, em essência, uma negação lógica da saída.) As classes dos terceiro e níveis mais altos da hierarquia são definidas dando-lhes ainda maisoráculosNP: Δ P k +

$$\begin{align*} \Delta_2^P &:= \mathsf{P}^{\mathsf{NP}}, \\ \Pi_2^P &:= \mathsf{coNP}^{\mathsf{NP}}. \end{align*}$$ Novamente, a diferença entre osoráculosΣPkeΠPké essencialmente a negação de sua produção. Também definimosΔP0=ΣP0=ΠP0=P; usando a definição acima, você pode ver que isso nos dáΔP1:=P,  ΣP1:=NPeΠP1:=c $$\begin{align*} \Delta_{k+1}^P &:= \mathsf{P}^{\,\Sigma_{k}^P} = \mathsf{P}^{\,\Pi_k^P}, \\[1ex] \Sigma_{k+1}^P &:= \mathsf{NP}^{\,\Sigma_{k}^P} = \mathsf{NP}^{\,\Pi_k^P}, \\[1ex] \Pi_{k+1}^P &:= \mathsf{coNP}^{\,\Sigma_{k}^P} = \mathsf{coNP}^{\,\Pi_k^P}. \\\end{align*}$$ $\Sigma_k^P$$\Pi_k^P$$\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mathsf{P}$$\Delta_1^P := \mathsf{P}$$\Sigma_1^P := \mathsf{NP}$ .$\Pi_1^P := \mathsf{coNP}$

$\Sigma_k^P$$\Pi_k^P$$\Pi_k^P$simulando alguma torre de oráculos NP ).

$\mathsf{NP}^{\mathsf{NP}}$

$\mathsf{NP}^{\mathsf{NP}} \supseteq \mathsf{coNP}$$\mathsf{NP} \supseteq \mathsf{coNP}$