Potenziell gleiche Komplexitätsklassen ohne bekannte widersprüchliche Relativierungen

16

Was sind einige Beispiele für Paare von Komplexitätsklassen und B, so dassAB

  1. wir wissen nicht, ob undA=B

  2. wir kennen auch keine widersprüchlichen Relativierungen (dh wir kennen keine Orakel und Q, so dass A P = B P und A QB Q )?PQAP=BPAQBQ

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?

Timothy Chow
quelle
1
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
2
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:

18

Ich denke , das größte solches Beispiel ist derzeit (quantum polybomial Zeit) vs P H (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 B Q P in P P ist .BQPPHBQ.PPP

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

Ryan Williams
quelle
3
Tatsächlich ist das bekannteste Ergebnis ist , wobei A W P P (unter anderem) die größte spalte definierbare sublcass von P P , so daß P P A W P P = P P . Ich kenne kein Interesse an der Klasse A W P P, abgesehen von ihrer Beziehung zu B Q P und P PBQ.PEINWPPPPEINWPPPPPPEINWPP=PPEINWPPBQ.PPP . Als Verfeinerung ist dies ein technischer Punkt, aber los geht's.
Niel de Beaudrap
2
In diesem Sinne ist es auch nicht bekannt, wie BQP von AM oder sogar QMA von AM getrennt werden kann.
Robin Kothari
5

Gibt es ein bekanntes Orakel, das von P S P A C E trennt ?P#PPSPACE

Ryan O'Donnell
quelle
6
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,
1
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