¿

10

¿Es con acceso oráculo a más grande que solo ? Según tengo entendido es sólo una máquina de Turing que se pueden realizar consultas a otro máquina si por lo que puede simular ? ¿Hay algo mal con este argumento? $NP$ $NP$ $NP$ $NP^ {NP}$ $NP$ $NP$ $NP^{NP}$

complexity-theory
fuente

16

La respuesta es que no lo sabemos , y el hecho de que aún no lo sepamos es un estado bastante bien establecido para este problema. La clase

también se conoce como

, y es una clase en el segundo nivel de la jerarquía polinómica . Una razón simple por la que no podemos simplemente simular un oráculo NP con una máquina NP es que no sabemos cómo la máquina NP podría detectar instancias "no".

{N P}^{N P}

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

Σ_{2}^{P}

$\Sigma^{P}_2$

¿Por qué

lo mismo que

?

N P^{N P}

$NP^{NP}$

Σ_{2}^{P}

$\Sigma_2^P$

55

Así es simplemente como se define

. Lea la página de Wikipedia o un libro de texto sobre la complejidad computacional que cubre la jerarquía polinómica.

Σ_{2}^{P}

$\Sigma_2^P$

13

Para reformular mis comentarios como respuesta y ampliar un poco:

No sabemos si NP ^NP = NP : es un problema notoriamente abierto en la teoría de la complejidad, aunque al igual que con P versus NP sospechamos que no son iguales. Una de las razones por las que no sabemos cómo simular un oráculo NP con una máquina NP es que no sabemos cómo la máquina NP podría detectar casos "no" de problemas enviados al oráculo.

La clase NP ^NP también se conoce como , y es una de las clases en el segundo nivel de la jerarquía polinómica . Las otras clases en el segundo nivel son $\Sigma_2^P$ (Todas estas clases serían las mismas siutilizáramosunoráculocoNP; la única diferencia es, en esencia, una negación lógica de la salida). Las clases del tercer y más alto nivel de la jerarquía se definen dándoles aún másoráculosNP:

\begin{aligned} Δ_{2}^{PAGS} & : = {PAGS}^{norte PAGS}, \\ Π_{2}^{PAGS} & : = {C o norte PAGS}^{norte PAGS} . \end{aligned}

$\begin{align*} \Delta_2^P &:= \mathsf{P}^{\mathsf{NP}}, \\ \Pi_2^P &:= \mathsf{coNP}^{\mathsf{NP}}. \end{align*}$

Nuevamente, la diferencia entre losoráculos

y

es esencialmente la negación de su salida. También definimos

; usando la definición anterior, puede ver que esto nos da

,

y

\begin{aligned} Δ_{k + 1}^{P} & := P^{Σ_{k}^{P}} = P^{Π_{k}^{P}}, \\ Σ_{k + 1}^{P} & := {N P}^{Σ_{k}^{P}} = {N P}^{Π_{k}^{P}}, \\ Π_{k + 1}^{P} & := {c o N P}^{Σ_{k}^{P}} = {c o N P}^{Π_{k}^{P}} . \end{aligned}

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

Σ_{k}^{P}

$\Sigma_k^P$

Π_{k}^{P}

$\Pi_k^P$

Δ_{0}^{P} = Σ_{0}^{P} = Π_{0}^{P} = P

$\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mathsf{P}$

Δ_{1}^{P} := P

$\Delta_1^P := \mathsf{P}$

Σ_{1}^{P} := N P

$\Sigma_1^P := \mathsf{NP}$

.

Π_{1}^{P} := c o N P

$\Pi_1^P := \mathsf{coNP}$

Se cree que las diversas clases de la jerarquía polinómica son distintas; es decir, no importa cuántas capas de oráculos NP proporcione, no se cree que la potencia computacional se estabilice en ningún momento. Si NP ^NP = NP , entonces la jerarquía polinómica se colapsa a su primer nivel : todas las clases de para k ≥ 1 serían iguales a NP (al igual que todas las clases de incluyendo coNP , como una máquina NP podría resolver cualquier problema en $\Sigma_k^P$ $\Pi_k^P$ $\Pi_k^P$ simulando alguna torre de oráculos NP ).

Niel de Beaudrap
fuente

5

se conoce como el segundo nivel dela jerarquía polinómica. $\mathsf{NP}^{\mathsf{NP}}$

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

sdcvvc
fuente

¿

Respuestas: