Potencjalnie równe klasy złożoności bez znanych sprzecznych relatywizacji

Jakie są przykłady par klas złożoności i , że $A$ $B$

nie wiemy, czy , i $A=B$
nie znamy też sprzecznych relatywizacji (tzn. nie znamy wyroczni i tak że i )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Aby sformułować pytanie w inny sposób, jakie są wyjątki od heurystyki, że jeśli nie uda się znaleźć sprzecznych relatywizacji, łatwo jest rozwiązać problem równości?

cc.complexity-theory complexity-classes relativization

— Timothy Chow
źródło

Czy jakieś dwie klasy A i B, dla których nie wiemy, jak udowodnić wyrocznię między A i B, wystarczą, aby odpowiedzieć na twoje pytanie? (Zakładając, że możliwe jest, aby A i B były równe.)

— Robin Kothari,

Czy zaakceptowałbyś przykłady dotyczące implikacji między równościami, a nie pojedynczych równości? Na przykład nie wiemy, czy NP = UP oznacza załamanie PH, ale nie mamy również wyroczni, w której ta implikacja jest fałszywa.

— Joshua Grochow

@JoshuaGrochow: To interesujące, chociaż nieco bardziej interesuje mnie konkretny rodzaj opisanego przeze mnie przykładu.

— Timothy Chow,

@Robin Kothari: Jeśli nie znamy wyroczni Q, a fortiori nie znamy wyroczni P i Q, więc jedynym sposobem, w jaki widzę (A, B), aby spełnić wasze wymagania, ale nie moje, jest to, że wiemy że A = B, ale nie znamy wyroczni, która je dzieli. Myślę, że może być interesujące zobaczyć przykład A i B taki, że A = B jest jednak prawdopodobne (ale nie wiadomo), że można je oddzielić wyrocznią, ale tak naprawdę nie o to prosiłem.

— Timothy Chow,

Odpowiedzi:

Myślę, że obecnie największym tego typu przykładem jest (kwantowy czas wielomianowy) vs (wielomianowa hierarchia czasu). Znaczny wysiłek włożono w rozdzielenie ich względem wyroczni, bez powodzenia. (Oczywiście na tyle mocny Oracle pozwoli im dorównać.), A najbardziej znanym jest fakt, że wynik powstrzymywanie w . $BQP$ $PH$ $BQP$ $PP$

Niektóre odniesienia do ataków na problem z wyrocznią: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

— Ryan Williams
źródło

Obecnie najbardziej znanym rezultacie

, gdzie

są (między innymi), największy sublcass szczelina definiowanych z

tak, że

. Nie znam żadnego zainteresowania klasą

poza jej związkiem z

B Q P \subseteq A W P P \subseteq P P

$\mathsf{BQP \subseteq AWPP \subseteq PP}$

A W P P

$\mathsf{AWPP}$

P P

$\mathsf{PP}$

P P^{A W P P} = P P

$\mathsf{PP^{AWPP} = PP}$

A W P P

$\mathsf{AWPP}$

B Q P

$\mathsf{BQP}$

P P

$\mathsf{PP}$ , więc w ramach udoskonalenia jest to trochę kwestia techniczna, ale proszę bardzo.

— Niel de Beaudrap,

Wzdłuż tych linii nie wiadomo również, jak oddzielić BQP od AM, a nawet QMA od AM.

— Robin Kothari,

Czy istnieje wyrocznia, która oddziela od ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

— Ryan O'Donnell
źródło

Jestem prawie pewien, że pytanie było zamierzone bardziej retorycznie, tj. „Myślę, że to odpowiedź, ale może znana jest wyrocznia, której nie jestem świadomy”

— Joshua Grochow,

Tak, dziękuję Josh. Czy znasz jeden Bardzo trudno jest szukać, ale pamiętam, że nie mogłem dowiedzieć się o swoim istnieniu ostatnim razem, gdy próbowałem.

— Ryan O'Donnell,