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$

$(\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 i , pod warunkiem, że jest powiązany z klasą standardowych maszyn, które w sposób naturalny uogólniają się na klasę maszyn wyroczni. W rzeczywistości klasa nie jest zdefiniowana na podstawie klasy ale raczej przez analogię do niej. W szczególności załóżmy, że $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 (tj. Tego typu i granic zasobów) i zbiór tak, że przyjmuje zestaw . $S \in C_1^{C_2}$ $M_1$ $S_2 \in C_2$ $M_1^{S_2}$ $S$

cc.complexity-theory complexity-classes

— MS Dousti
źródło

Ale… czy

tym samym co

? A może coś tu brakuje?

({N P}^{N P})^{N P}

$(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$

{N P}^{N P}

$\mathbf{NP}^{\mathbf{NP}}$

— Antonio E. Porreca,

Strzeż się niebezpieczeństw związanych z notacją wyroczni. Nie zdefiniowaliśmy pojęcia dołączania wyroczni do żadnej klasy języków. Tylko do klas języków zdefiniowanych przez model obliczeniowy, do których można dołączyć wyrocznie. Zatem w pewnym sensie

nie jest od razu dobrze zdefiniowane.

(N P^{N P})^{N P}

$(NP^{NP})^{NP}$

— Kristoffer Arnsfelt Hansen

Cóż, zgadzam się, że zwykłe pojęcie „stawianie

jako wykładnika klasy” jest ogólnie źle zdefiniowane. Ale bazowy model obliczeniowy

jest dobrze zdefiniowany (polytime NTM z wyrocznią dla jakiegoś problemu z kompletnością

) i dodanie do niego kolejnej wyroczni, jak w

, wydaje się proste do mnie. Zakładając tę interpretację, miałem na myśli to, że druga wyrocznia jest zbędna. Z przyjemnością dowiem się, czy symbol

dopuszcza inne interpretacje.

N P

$\mathbf{NP}$

{N P}^{N P}

$\mathbf{NP}^{\mathbf{NP}}$

N P

$\mathbf{NP}$

({N P}^{N P})^{N P}

$(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$

({N P}^{N P})^{N P}

$(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$

— Antonio E. Porreca,

Prawo to, zgodnie z tą interpretacją, klasa się nie zmieni. Nie jest to jednak poprawna interpretacja do relatywizacji dowodu Lautemansa, jak uczyniono to w artykule wspomnianym w pytaniu.

— Kristoffer Arnsfelt Hansen

Sadeq: Nikt nie twierdzi, że stwierdzenie w gazecie jest błędne.

— Kristoffer Arnsfelt Hansen

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 (przez Mam na myśli wyrocznię albo do albo do język). $(NP^{NP})^{A}$ $(NP^{NP^A\cup A})$ $\cup$ $A$ $NP^A$

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

— Arthur MILCHIOR
źródło

Przepraszam, nie rozumiem Czy możesz wyjaśnić coś więcej?

— MS Dousti,

Mam nadzieję, że edycja stanie się bardziej

— sensowna

Bardzo dobrze dziękuję. To ma sens.

— MS Dousti,

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

— Marcos Villagra
źródło