Przykład czegoś innego dla ogólnych i losowych wyroczni?

Niech będzie ogólną wyrocznią w sensie kategorii Cohen / Baire. Niech będzie losową wyrocznią. $G$ $R$

Czy istnieją klasy złożoności A i B z lub na odwrót,

A^{G} = B^{G} and A^{R} \neq B^{R}

$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$

A^{G} \neq B^{G} and A^{R} = B^{R} ?

$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$

Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .

cc.complexity-theory complexity-classes Bjørn Kjos-Hanssen
źródło

Odpowiedzi:

P = UP z ogólnym (zakładając, że P = PSPACE), ale są one oddzielne w stosunku do losowej wyroczni.

W drugim kierunku P = Obietnica-BPP względem losowego, ale oddzielnego względem ogólnego. Nie mogę sobie wyobrazić non-obiecującej klasy z mojej głowy.

W razie potrzeby mogę wyśledzić niektóre referencje.

Aktualizacja: jeśli chcesz wersji bez obietnicy, z losową wyrocznią (ponieważ ), ale oddzielają się ogólną wyrocznią (przykład w mojej pracy z Yamakami ). $P^{NP} = S^p_2$ $S^p_2 \subseteq ZPP^{NP}$

Lance Fortnow
źródło

P = PSPACE wydaje się odważnym założeniem;)

Bjørn Kjos-Hanssen

Aby wyjaśnić komentarz Bjorna: innym sposobem na wyrażenie tego jest najpierw relatywizacja do wyroczni PSPACE, następnie zbudowanie ogólnego, a następnie otrzymanie P = UP. Istnieje więc ogólna wyrocznia (w stosunku do PSPACE-), która powoduje, że P = UP.

Joshua Grochow

Dodałem nieprzyrzeczony przykład. Musisz także przyjąć pewne założenie, ponieważ jeśli P UP w świecie nierelatywizowanym, to pozostają one inne w stosunku do ogólnych. Lub możesz użyć sztuczki Josha.

\neq

$\neq$

Lance Fortnow,

Nie sądzę, abyśmy znali bezwarunkowe różnice klas złożoności jednorodnej / nonpromise w powyższej formie (aktualizacja: patrz odpowiedź Lance'a Fortnowa dla przykładu), ale poniższe porównanie ogólnych wyroczni z losowymi wyroczniami może być pomocne.

Ogólna wyrocznia polega na zbudowaniu wyroczni, która spełnia każdą właściwość , której nie można wykluczyć poprzez ustalenie skończonego segmentu początkowego. W pewnym sensie dzieje się wszystko, co jest koniecznie możliwe, co bardzo różni się od losowej wyroczni (chociaż nieskończenie często emuluje losową wyrocznię). $Σ^0_1$

Na przykład z ogólną wyrocznią (io oznacza nieskończenie często)
PSPACE ⊆ io-P
EXP ⊆ io-ZPP
EXP ^NP ⊆ io-BPP

Zatem dla każdego problemu w relatywizowanym PSPACE istnieje algorytm wielomianowy (wykorzystujący wyrocznię), który dla nieskończenie wielu rozmiarów wejściowych rozwiązuje wszystkie wystąpienia tego rozmiaru (i podobnie w przypadku ZPP i BPP z dowolnym zachowaniem przy „złych” rozmiarach wejściowych) .

Podobnie jak losowa wyrocznia:
IP <PSPACE
Hierarchia wielomianowa jest nieskończona.

Każda funkcja rekurencyjna obliczalna w czasie wielomianowym z ogólną wyrocznią jest obliczalna w czasie wielomianowym bez wyroczni (ponieważ wyrocznia jest pusta na wystarczająco długie odcinki). Zatem jeśli P <BPP, to dotyczy to również ogólnej wyroczni, podczas gdy dla losowej wyroczni P = BPP.

Dmytro Taranovsky
źródło

Co rozumiesz przez = io między klasami języków?

Kaveh

Czyli przez „P = ioPSPACE” masz na myśli PSPACE ioP? To dość mylące. Dlaczego przeniosłeś prefiks io do innej klasy?

\subseteq

$\subseteq$

Emil Jeřábek

@Kaveh A = io B oznacza, że istnieje nieskończony zbiór S taki, że A ⊆ SB i B ⊆ SA (gdzie SB jest zdefiniowane analogicznie do io-B). Ponieważ jednak to użycie jest niestandardowe, zmieniłem odpowiedź na użycie ⊆ io

Dmytro Taranovsky

@ EmilJeřábek Zastąpiłem = io standardowym ⊆ io

Dmytro Taranovsky

Wiem, co to znaczy dla języków, pytam, co to znaczy dla klas języków. io-C ma sens dla klasy C, = io jako relacja wydaje się nie mieć sensu, jak pierwotnie pisałeś.

Kaveh