¿Es

En el "último párrafo" de la "primera página" del siguiente documento:

Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , "Si NP tiene circuitos de tamaño polinómico, entonces MA = AM", Ciencias de la computación teóricas, 1995.

Encontré una afirmación algo contraintuitiva:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

Creo que la identidad anterior se deduce de lo siguiente:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

y

$(\Pi^P_2)^{NP} = \Pi^P_3$

El primero se escribe más simplemente como , ¡lo cual es bastante extraño!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Editar: A la luz del comentario de Kristoffer a continuación, me gustaría agregar el siguiente comentario inspirador del libro de complejidad de Goldreich (pp. 118-119):

Debe quedar claro que la clase se puede definir para dos clases de complejidad C 1 y C 2 , siempre que C 1 esté asociado con una clase de máquinas estándar que se generalice naturalmente a una clase de máquinas Oracle. En realidad, la clase C C 2 1 no está definida en base a la clase C 1 sino más bien por analogía. Específicamente, suponga que C $C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$es la clase de conjuntos que son reconocibles (o más bien aceptados) por máquinas de cierto tipo (por ejemplo, deterministas o no deterministas) con ciertos límites de recursos (por ejemplo, límites de tiempo y / o espacio). Luego, consideramos máquinas oracle análogas (es decir, del mismo tipo y con los mismos límites de recursos), y decimos que si existe una máquina oracle adecuada M 1 (es decir, de este tipo y límites de recursos) y un conjunto S 2 ∈ C 2 tal que M S 2 1 acepta el conjunto S .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

es el conjunto de lenguaje decidido por una máquina de turing alterna en estado existencial y luego universal, con un oráculo en NP. Tanto la parte universal como la existancial pueden consultar NP.${\Sigma_2^P}^{NP}$

Por lo tanto, en este caso, decidió escribir esto como entonces la forma en que debe pensar es como ( $(NP^{NP})^{A}$ (por ∪ me refiero a un oráculo para A o para un N P A idioma).$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

Por lo tanto es igual a ( N P ( N P N P ) ) N P que sin duda es igual a ( N ${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$ya que cada consulta se podría hacer a laNPoráculo, que podría hacer aloráculo deN P N $(NP^{NP^{NP}})$$NP$$NP^{NP}$

Del teorema 5.12 de Arora y Barak (p. 102): "Por cada $i\geq 2$$\sum_i^p=NP^{\sum_{i-1}SAT}$$\sum_{i}SAT$$i$$\sum_i^p$$\sum_2^p=NP^{SAT}$$\sum_2^p=NP^{NP}$$i=3$$NP^{NP^{NP}}$$\sum_{2}SAT$