Czy wyroki są stowarzyszone?

To pytanie może mieć oczywistą odpowiedź ... ale oto i tak pytanie. Intuicyjnie jest to następujące prawdopodobne stwierdzenie - „maszyna z podprogramem A, który z kolei ma podprogram B, jest tym samym, co maszyna z podprogramem A, który ma dostęp do podprogramu B”.

Aby formalnie zdefiniować ten problem, użyję niekonwencjonalnej notacji. Kiedy mówię $A^B$ , daję $A$ wyrocznię za problem $B-Complete$ . np. $NP^{NP}=NP^{SAT}=\Sigma_2$ . Za pomocą tej „nowej” notacji można zdefiniować $A^{B^C}$ i tak dalej. Moje pytanie brzmi: jest

• czy jest to prawidłowy sposób myślenia o wyroczniach?
• to $(A^B)^C = A^{(B^C)}$

Na przykład $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$

Nie mogę wymyślić żadnych oczywistych kontrprzykładów tej zasady. Ktoś?

Jak powiedział Venkat w komentarzach, wydaje się, że trudno jest zrozumieć twoją definicję wyroczni, która nie jest zdefiniowana jako pewna charakterystyka maszyny.

Niech będzie zbiorem TM w A z wyrocznią, która jest maszyną w ( B z wyrocznią w maszynie w C ). Jest oczywiste, że maszyna w A mogą dzwonić C : to właśnie nazywa się maszynę w B i prosi go, aby nieść wiadomość bezpośrednio do C .$A^{(B^C)}$$A$$B$$C$$A$$C$$B$$C$

Myślę, że byłaby maszyną w A, która może wywoływać wyrocznię w C lub wyrocznią, która jest (maszyna w B, która może wywoływać maszynę w C ), więc jest to dokładnie ta sama definicja.${(A^B)}^C$$A$$C$$B$$C$

Wreszcie, możesz chcieć , który z pewnością różni się od pozostałych dwóch (wystarczy wziąć B = C = N P i A = P , następnie A B , C = N P ∪ c o N P podczas gdy A ( B C ) = Σ P 2 ∪ Π p 2 .$A^{B,C}$$B=C=NP$$A=P$$A^{B,C}=NP\cup coNP$$A^{(B^C)}=\Sigma_2^P\cup\Pi_2^p$

Chciałbym napisać następujący komentarz, ale było to zbyt długie, aby zmieściło się w nim.

Najpierw opiszmy znaczenie „algorytmów w klasie z wyrocznią dla języka A.” (Potrzeba tego została wskazana przez Tsuyoshi Ito). Będziemy korzystać z tej samej konwencji, z której korzystają Ladner i Lynch . Konwencja jest dobrze opisana przez Bennett & Gill :$\bf C$

można zdefiniować na różne sposoby, w zależności od tego, jak obsługiwana jest taśma zapytania. Przestrzegamy konwencji Ladnera i Lyncha [LL]: Taśma zapytania nie jest obciążana ograniczeniem miejsca, ale aby nie była używana jako taśma robocza, taśma zapytania jest jednokierunkowa i tylko do zapisu i jest usuwana automatycznie po każdym zapytaniu. (Simon [Si] traktuje taśmę zapytania jako jedną z taśm roboczych, dwukierunkową taśmę do odczytu / zapisu obciążoną ograniczeniem przestrzeni. Definicja Ladner-Lynch jest mniej restrykcyjna i być może bardziej naturalna, ponieważ dla losowej wyroczniA∈ L O G S P A C E$\bf{LOGSPACE}^A$$A \in \bf{LOGSPACE}^A$ trzyma z prawdopodobieństwem 1 dla [LL], ale nie dla [Si])

[LL] RE LADNER I NA LYNCH, Relatywizacja pytań o obliczalność przestrzeni logów , Matematyka. Systems Theory, 10 (1976), s. 19–32.

[Si] J. SIMON, On Some Central Problems in Computational Complexity , Tech. Rep TR 75-224, Wydział Informatyki, Cornell University, Ithaca, NY, 1975.

Standardowa definicja klas złożoności maszyn Oracle jest następująca: Niech B i C będą klasami złożoności . Następnie jest uzasadniony klasa złożoności, określone jako X = ⋃ L ∈ C B L . Tutaj B L reprezentuje klasę złożoności problemów decyzyjnych rozwiązanych przez algorytm w klasie B z wyrocznią dla języka L.$X = B^C$$X = \bigcup_{L\in C}{B^L}$$B^L$

Ponieważ X jest uzasadniony klasa złożoności, dla każdej klasy A złożoność, możemy mówić o klasami złożoności i X A = ( B C ) A .$A^X = A^{(B^C)}$$X^A = (B^C)^A$

• odnosi się do klasy złożoności problemów decyzyjnych rozwiązany przez algorytm w klasie A z Oracle dla dowolnego języka$A^X$ . Innymi słowy, A X = ⋃ L ′ ∈ { ⋃ L ∈ C B L } A L ′ .$L' \in X = \bigcup_{L\in C}{B^L}$$A ^ X = \bigcup\limits_{L'\in \{\bigcup\limits_{L\in C}{B^L}\}}{A^{L'}}$

• odnosi się do klasy złożoności problemów decyzyjnych możliwych do rozwiązania przez algorytm z klasy X = ⋃ L ∈ C B L z wyrocznią dla dowolnego języka L ′ ∈ $X^A$$X = \bigcup_{L\in C}{B^L}$$L' \in A$ . Innymi słowy, .$X ^ A = \bigcup_{L' \in A} {{X^{L'}}} = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}}$

Zastrzeżenie: .$(B^{L_1})^{L'} \cup (B^{L_2})^{L'} = (B^{L'})^{L_1 \cup L_2}$

Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.

Dlatego można napisać .$X ^ A = \bigcup_{L' \in A} {{{\left( {\bigcup_{L \in C} {{B^L}} } \right)}^{L'}}} = \bigcup_{L \in C, L' \in A} {{{\left( B^{L'} \right)}^L}}$

Przykład

Niech . Wiemy, żeco,NP⊆X. Dając dostęp zarówno boki ORACLENP, dostaje:CON P N P ⊆ X N P =( P N P ) N P .$\bf X = \bf{P^{NP}}$$\bf{coNP} \subseteq \bf X$$\bf {NP}$$\bf{coNP^{NP}} \subseteq \bf{X^{NP}} = (\bf{P^{NP}})^{\bf{NP}}$

Epilog

Owocna dyskusja z Tsuyoshi Ito ujawniła (dla mnie), że podwójna relatywizacja klasy złożoności nie jest łatwa. W rzeczywistości nawet zdefiniowanie jednego wydaje się problematyczne. Powinienem zdecydowanie przestudiować więcej, aby zobaczyć, czy kiedykolwiek zostanie podana zadowalająca definicja. Tymczasem doceniam każdy komentarz, który można wykorzystać do rozwiązania tego problemu.