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


11

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

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

AG=BGandARBR
AGBGandAR=BR?

Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .

Odpowiedzi:


12

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 ).PNP=S2pS2pZPPNP


3
P = PSPACE wydaje się odważnym założeniem;)
Bjørn Kjos-Hanssen

4
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.
Lance Fortnow,

4

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ę).Σ10

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.


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

1
Czyli przez „P = ioPSPACE” masz na myśli PSPACE ioP? To dość mylące. Dlaczego przeniosłeś prefiks io do innej klasy?
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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.