É ?

No "último parágrafo" da "primeira página" do seguinte artigo:

Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , "Se NP possui circuitos de tamanho polinomial, então MA = AM", Ciência da Computação Teórica, 1995.

Eu encontrei uma afirmação um tanto contra-intuitiva:

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

Eu acho que a identidade acima é deduzida do seguinte:

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

e

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

O primeiro é mais simplesmente escrito como , o que é bastante estranho!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Editar: À luz do comentário de Kristoffer abaixo, eu gostaria de acrescentar a seguinte observação inspiradora do livro de complexidade de Goldreich (pp. 118-119):

Deve ficar claro que a classe pode ser definida para duas classes de complexidade e , desde que esteja associado a uma classe de máquinas padrão que generaliza naturalmente a uma classe de máquinas Oracle. Na verdade, a classe não é definida com base na classe mas sim por analogia. Especificamente, suponha que C 1 C 2 C 1 C C $C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$é a classe de conjuntos reconhecíveis (ou melhor, aceitos) por máquinas de um determinado tipo (por exemplo, determinístico ou não determinístico) com determinados limites de recursos (por exemplo, limites de tempo e / ou espaço). Então, consideramos máquinas oracle análogas (ou seja, do mesmo tipo e com os mesmos limites de recursos) e dizemos que se existe uma máquina oracle adequada (ou seja, deste tipo e limites de recursos ) e um conjunto de de tal modo que H S 2 uma aceita o conjunto S .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

é o conjunto de linguagem decidida por uma máquina rees alternada em existencial, e, em seguida, estado universal, com um Oracle no NP. Tanto a parte universal quanto a existente podem consultar NP.${\Sigma_2^P}^{NP}$

Portanto, neste caso, você decidiu escrever isso como então a maneira como você deve pensar nisso é como ( N P N P A ∪ A ) (por ∪ quero dizer um oráculo para A ou para um N P Um idioma).$(NP^{NP})^{A}$$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

Assim é igual a ( N P ( N P N P ) ) N P o que certamente é igual a ( N P N P N P ) uma vez que cada consulta que você poderia dar para o N P Oracle, você poderia fazê-lo ao oráculo N P N ${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$$(NP^{NP^{NP}})$$NP$$NP^{NP}$

De Arora e Barak (p 102). Teorema 5,12: "Para cada , Σ p i = N P Σ i - 1 S A T ". Lembrar que Σ i S A T é a fórmula QBF com i alternâncias que se completa para Σ p i . Então Σ p 2 = N P S A T e dado que SAT é NP-completa você acabou de escrever Σ p 2 = N P $i\geq 2$$\sum_i^p=NP^{\sum_{i-1}SAT}$$\sum_{i}SAT$$i$$\sum_i^p$$\sum_2^p=NP^{SAT}$ , até agora tudo bem. Ao estender essa notação parai=3,você obtémN P N P N P , mas os dois últimos "NPs" são apenas um oráculo para a linguagem ∑ 2 SATcom no máximo 2 alternações. Parece-me que é apenas uma notação abreviada para acesso ao oráculo.$\sum_2^p=NP^{NP}$$i=3$$NP^{NP^{NP}}$$\sum_{2}SAT$