Czy

W „ostatnim akapicie” „pierwszej strony” następującego artykułu:

Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , „Jeśli NP ma obwody wielomianowe, wówczas MA = AM”, Theoretical Computer Science, 1995.

Napotkałem nieco sprzeczne z intuicją twierdzenie:

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

Myślę, że powyższa tożsamość została wydedukowana z następujących elementów:

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

i

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

To pierwsze jest prostsze niż jako , co jest dość dziwne!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Edycja: W świetle poniższego komentarza Kristoffera chciałbym dodać następującą inspirującą uwagę z książki o złożoności Goldreicha (str. 118-119):

Powinno być jasne, że klasę można zdefiniować dla dwóch klas złożoności C 1 i C 2 , pod warunkiem, że C 1 jest powiązany z klasą standardowych maszyn, które w sposób naturalny uogólniają się na klasę maszyn wyroczni. W rzeczywistości klasa C C 2 1 nie jest zdefiniowana na podstawie klasy C 1, ale raczej przez analogię do niej. W szczególności załóżmy, że C $C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$to klasa zbiorów, które są rozpoznawalne (lub raczej akceptowane) przez maszyny określonego typu (np. deterministyczne lub niedeterministyczne) z pewnymi granicami zasobów (np. granicami czasu i / lub przestrzeni). Następnie rozważamy analogiczne maszyny wyroczni (tj. Tego samego typu i z tymi samymi granicami zasobów) i mówimy, że jeśli istnieje odpowiednia maszyna wyroczni M 1 (tj. Tego typu i granic zasobów) i zbiór S 2 ∈ C 2 tak, że K S 2 1 przyjmuje zestaw S .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

jest zbiorem języka ustalanym przez przemienną maszynę Turinga w stanie egzystencjalnym, a następnie uniwersalnym, z wyrocznią w NP. Zarówno część uniwersalna, jak i egzystencjalna mogą wyszukiwać NP.${\Sigma_2^P}^{NP}$

Dlatego w tym przypadku zdecydowałeś się napisać to jako to sposób, w jaki powinieneś o tym myśleć, to ( N P N P A ∪ A ) (przez ∪ Mam na myśli wyrocznię albo do A, albo do N P A język).$(NP^{NP})^{A}$$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

Stąd jest równe ( N P ( N P N P ) ) N P, które z pewnością jest równe ( N P N P N P ), ponieważ każde zapytanie, które możesz zadać do N P wyroczni, możesz to zrobić do N P N P oracle.${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$$(NP^{NP^{NP}})$$NP$$NP^{NP}$

$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$