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,