Potenziell gleiche Komplexitätsklassen ohne bekannte widersprüchliche Relativierungen

Was sind einige Beispiele für Paare von Komplexitätsklassen und so dass $A$ $B$

wir wissen nicht, ob und $A=B$
wir kennen auch keine widersprüchlichen Relativierungen (dh wir kennen keine Orakel und so dass und )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Um die Frage anders auszudrücken: Was sind einige Ausnahmen von der Heuristik, dass es einfach ist, die Gleichstellungsfrage direkt zu lösen, wenn sich widersprüchliche Relativierungen nicht herausstellen lassen?

cc.complexity-theory complexity-classes relativization Timothy Chow
quelle

Würden zwei Klassen A und B, für die wir keine Orakeltrennung zwischen A und B nachweisen können, ausreichen, um Ihre Frage zu beantworten? (Vorausgesetzt, es ist möglich, dass A und B gleich sind.)

Robin Kothari

Würden Sie Beispiele über Implikationen zwischen Gleichheiten und nicht einzelne Gleichheiten akzeptieren? Zum Beispiel wissen wir nicht, ob NP = UP impliziert, dass PH zusammenbricht, aber wir haben auch kein Orakel, in dem diese Implikation falsch ist.

Joshua Grochow

@JoshuaGrochow: Das ist interessant, obwohl ich mich etwas mehr für die spezifische Art von Beispiel interessiere, die ich beschrieben habe.

Timothy Chow

@Robin Kothari: Wenn wir kein Orakel Q kennen, kennen wir erst recht keine Orakel P und Q, daher sehe ich für (A, B) nur eine Möglichkeit, Ihre Anforderungen zu erfüllen, meine jedoch nicht, wenn wir es wissen dass A = B, aber wir kennen kein Orakel, das sie trennt. Ich denke, es könnte interessant sein, ein Beispiel für A und B so zu sehen, dass A = B, aber es ist plausibel (aber nicht bekannt), dass sie durch ein Orakel getrennt werden könnten, aber das ist nicht wirklich das, wonach ich gefragt habe.

Timothy Chow

Antworten:

Ich denke , das größte solches Beispiel ist derzeit (quantum polybomial Zeit) vs (die Polynom Zeithierarchie). Es wurden erhebliche Anstrengungen unternommen, um sie in Bezug auf ein Orakel zu trennen, ohne Erfolg. (Ein Orakel, das stark genug ist, wird sie natürlich gleich machen.) Und das bekannteste Eindämmungsergebnis ist, dass in . $BQP$ $PH$ $BQP$ $PP$

Einige Hinweise für Angriffe auf das Oracle-Problem: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

Ryan Williams
quelle

Tatsächlich ist das bekannteste Ergebnis ist

, wobei

(unter anderem) die größte spalte definierbare sublcass von

, so daß

. Ich kenne kein Interesse an der Klasse

abgesehen von ihrer Beziehung zu

und

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}$ . Als Verfeinerung ist dies ein technischer Punkt, aber los geht's.

Niel de Beaudrap

In diesem Sinne ist es auch nicht bekannt, wie BQP von AM oder sogar QMA von AM getrennt werden kann.

Robin Kothari

Gibt es ein bekanntes Orakel, das von trennt ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

Ryan O'Donnell
quelle

Ich bin mir ziemlich sicher, dass die Frage eher rhetorisch gedacht war, dh "Ich denke, das ist eine Antwort, aber vielleicht ist ein Orakel bekannt, von dem ich nichts weiß"

Joshua Grochow,

Ja, danke Josh. Kennst du einen? Es ist sehr schwer zu suchen, aber ich erinnere mich, dass ich beim letzten Versuch nicht in der Lage war, etwas über meine Existenz zu erfahren.

Ryan O'Donnell