Wyniki Oracle dla P vs BPP

10

Niech będzie dowolnym EXP kompletnym problemem. Następnie . $A$ $P^A = NP^A$

Niech będzie jakiś wyrocznią, która bierze pod rachunkach zapytań (a TM w P) uczynią, a my możemy dostać . $B$ $M$ $P^B \neq NP^B$

Pytanie: Czy mamy podobne wyniki wyroczni dla P vs BPP?

cc.complexity-theory oracles relativization Kaveh
źródło

2

Tak, ale nie jestem pewien, czy mogę znaleźć cytat. (Cóż, pierwsza część jest łatwa, daj obu klasom wyrocznię za problem z EXP).

Robin Kothari

3

Jeśli myślisz o ustawieniu PCP jako weryfikator mający oracle dostęp do Prover (gdzie Oracle kwerendy wróci do kawałek dowodu) to wiemy, że jeśli pozwoli weryfikator być maszyna BPP z losowości i zapytania następnie klasa języków obliczane jest i gdy weryfikator jest maszyną P (który ma przypadkowości) z (nawet z ) odpytuje wtedy klasa języków obliczana jest . Nie pokazuje to separacji wyroczni, chyba że . Ale to tylko przykład, w którym dostęp Oracle do „wydaje się” silniejszy.

i

$i$

i^{t h}

$i^{th}$

\log n

$\log n$

3

$3$

N P

$NP$

3

$3$

\log n

$\log n$

P

$\bf P$

P \neq N P

$\bf P \neq \bf NP$

B P P

$\bf BPP$

Sajin Koroth

@RobinKothari Niech a jeśli jest jakikolwiek problem z , nie mamy (ostatnia nierówność według hierarchii czasu)? Czy gdy wyświetlany jest ?

\oplus P = N P = E X P

$\oplus P=NP=EXP$

A

$A$

E X P

$EXP$

N P^{A} = N P^{\oplus P} = \oplus P^{\oplus P} = \oplus P = N P = E X P \neq P

$NP^A=NP^{\oplus P}=\oplus P^{\oplus P}=\oplus P=NP=EXP\neq P$

P^{A} = N P^{A} ⟹ P^{\oplus P} = N P = \oplus P

$P^A=NP^A\implies P^{\oplus P}=NP=\oplus P$

P \neq N P

$P\neq NP$

T ....

13

Miałem niejasne wspomnienie, że znałem doskonałe odniesienie do takich podziałów wyroczni. W końcu to znalazłem.

Doskonałym odniesieniem do separacji wyroczni (dla klas między P i PSPACE) jest następujący artykuł :

Vereshchagin, NK (1994), „ZWIĄZANE I NIEZWIĄZANE TEOREMY W POLYNOMIALNEJ TEORII ALGORYTMÓW”, Rosyjska Akademia Nauk. Izvestiya Mathematics 42 (2): 261

Artykuł pokazuje (lub przytacza cytat) separację wyroczni pomiędzy prawie każdą parą klas, na których możesz się martwić między P i PSPACE (np. Zawiera klasy takie jak P, RP, BPP, UP, FewP, NP, MA, AM , inne poziomy PH, PH, IP, PSPACE itp.).

Na przykład Twierdzenie 8 pokazuje problem z wyrocznią w coRP, który nie występuje w NP. Ponieważ (w stosunku do wszystkich wyroczni) coRP jest w BPP, a NP zawiera P, otrzymujemy problem z wyrocznią w BPP, który nie jest w P.

Jak wspomniałem w moim komentarzu, pokazanie wyroczni, dla której jest łatwe. Niech A będzie językiem kompletnym EXP lub językiem kompletnym PSPACE. $\text{P}^A = \text{BPP}^A$

Robin Kothari
źródło

tutaj jest bezpłatny link do pobrania z citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232

Marcos Villagra

Chociaż jeśli możesz uzyskać pełną wersję, polecam ją zamiast tego. Wersja cytatowa nie ma danych liczbowych, dlatego brakuje w niej ładnego schematu włączenia klasy złożoności (ryc. 1).

Robin Kothari,

8

Złożoność zoo jest twoim przyjacielem! Jak powiedział Robin, masz połowę odpowiedzi: jakikolwiek problem z EXP zwija NP do P, a zatem BPP do P. Buhrman i Fortnow skonstruowali wyrocznię, dla której P = RP, ale BPP nie jest równe P. To więcej niż o co prosiłeś; Podejrzewam, że istnieją łatwiejsze konstrukcje, które oddzielają P od RP i BPP.

Sasho Nikolov
źródło

6

Dobry opis wyroczni, która oddziela P i BPP, podał Greg Kuperberg w jednym z komentarzy tego interesującego postu na blogu , w którym Terence Tao opisuje maszyny Turinga z wyroczniami i złożonością wynikającą z wyroczni w formie alegorii.

Alessandro Cosentino
źródło

1

to fajny opis :)

Sasho Nikolov

-1

Bennett i Gill wydają wyroki w obu przypadkach: http://epubs.siam.org/doi/abs/10.1137/0210008

Luke Mathieson
źródło

Czy dają wyrocznię, aby oddzielić BPP od P? Nie mogłem znaleźć takiego roszczenia w gazecie.

Robin Kothari,

Tak myślałem, niestety nie ma mnie w biurze, więc nie mam dostępu do pliku pdf. Będę musiał sprawdzić później.

Luke Mathieson

Całkiem słuszne, pokazują tylko przypadek . Mój błąd.

B P P^{A} = P^{A}

$BPP^{A} = P^{A}$

Luke Mathieson

Wyniki Oracle dla P vs BPP

Odpowiedzi: