Niech będzie ogólną wyrocznią w sensie kategorii Cohen / Baire. Niech będzie losową wyrocznią.
Czy istnieją klasy złożoności A i B z lub na odwrót,
Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .
Niech będzie ogólną wyrocznią w sensie kategorii Cohen / Baire. Niech będzie losową wyrocznią.
Czy istnieją klasy złożoności A i B z lub na odwrót,
Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .
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 ).
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ę).
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.