Wie wir wissen, ist der Graphisomorphismus in NP, aber es ist nicht bekannt, dass er NP-vollständig oder P-vollständig ist. Ich habe mich gefragt, ob es Probleme gibt, von denen bekannt ist, dass sie in PSPACE vorhanden sind, von denen jedoch nicht bekannt ist, dass sie PSPACE-vollständig sind und nicht in PH liegen.
cc.complexity-theory
complexity-classes
Tayfun Pay
quelle
quelle
Antworten:
Es ist bekannt, dass die existentielle Theorie der Reals in PSPACE enthalten ist, aber es ist nicht bekannt, ob sie in PH enthalten ist. Nehmen wir also die existentielle Theorie der Realitäten oder eines der vielen äquivalenten Probleme.
quelle
quelle
Meinen Kommentar kopieren:
Wenn Sie nach einem Problem analog zu GI fragen wollten, dann fragen Sie vielleicht nach einem Problem, das nicht in PH und nicht PSPACE-vollständig ist. Als Beispiel dienen Probleme, die für eine Klasse abgeschlossen sind, von der nicht bekannt ist, dass sie in PH, aber in PSPACE enthalten ist. Nehmen Sie also jedes Problem für BQP, QMA, PP usw. vollständig.
quelle
Jedes Problem, das MP-vollständig ist. Die Klasse der Entscheidungsprobleme, so dass für einige # P-Funktionen f die Antwort auf Eingabe x genau dann 'Ja' ist, wenn das mittlere Bit von f (x) 1 ist. [Definition ist von Komplexitätszoo].
Es wurde gezeigt, dass PH ⊆ MP ⊆ PSPACE.
quelle
Das ParitySat-Problem besteht darin, zu überprüfen, ob ein SAT-Problem eine ungerade Anzahl von erfüllbaren Zuweisungen aufweist. PH ist durch randomisierte Reduktionen durch Todas Arbeit auf ParitySAT reduzierbar. Dies ist ein Entscheidungsproblem, das eindeutig streng zwischen PH und PSACE liegt, sofern PH nicht zusammenbricht.
quelle