Gibt es ein Rechenproblem, das quasi-polynomial ist, aber (vielleicht) nicht in ?

Quasi-Polynomialzeit, kurz QP, ist eine Komplexitätsklasse auf deterministischen Turing-Maschinen. Hier ist die genaue Definition: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

Während βP eine Komplexitätsklasse mit begrenztem Nichtdeterminismus ist. Hier ist die genaue Definition: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Es ist leicht zu erkennen, dass jede Maschine von βP durch eine Maschine von QP simuliert werden kann, nämlich βP QP. $\subseteq$

Aber haben wir ein Beispiel, ein Problem, das in QP, aber nicht in βP liegt, auch wenn wir keinen genauen Beweis dafür haben, dass das Problem nicht in βP liegt?

cc.complexity-theory complexity-classes Arthur Kexu-Wang
quelle

Sei f die Funktion number_of_states_ und betrachte das Problem " M höchstens an (f (M)) Schritte? " .

$\hspace{2.36 in}$

^{\log (f (M))}

$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$

Antworten:

Obwohl ich in kein spezifisches (vermutetes) Beispiel , gibt es immer noch überzeugende Beweise dafür, dass eine geeignete Teilmenge von . Diese Klassen verhalten sich nämlich in ihrer Beziehung zu sehr unterschiedlich : $QP-\beta P$ $\beta P$ $QP$ $NP$

$\bullet$ Aus der Definition geht hervor, dass . $\beta P\subseteq NP$

$\bullet$ Auf der anderen Seite ist nicht bekannt, und es wäre sehr schwer zu beweisen, da es impliziert . (Tatsächlich ist es eine noch stärkere Aussage als .) $QP\subseteq NP$ $P\neq NP$ $P\neq NP$

Solch ein ganz anderes Verhalten im Vergleich zu scheint einen ziemlich starken Grund zu der Annahme zu liefern, dass . $NP$ $\beta P\neq QP$

Andras Farago
quelle

Es ist auch unwahrscheinlich, dass unter Komplement geschlossen wird.

β P

$\beta P$

Emil Jeřábek

Da, wie Sie erwähnt haben, impliziert . Was würde das Ergebnis von oder in der Komplexitätshierarchie bedeuten und würde es Auswirkungen auf das Problem haben?

Q P \subseteq N P

$QP\subseteq NP$

P \neq N P

$P\neq NP$

N P \subseteq Q P

$NP \subseteq QP$

N P \subset Q P

$NP \subset QP$

P v s N P

$P vs NP$

TheoryQuest1

Ja. Wir haben ein solches Problem. Es ist ein Graph-Isomorphismus-Problem. Babai hat bewiesen, dass GI in QP ist . Mein Verständnis ist, dass Babais Beweis keine begrenzte Obergrenze des Nichtdeterminismus ( ) für die Komplexität von GI ergibt . $\beta P$

Wir haben keinen Beweis dafür, dass GI in $\beta P$ . Darüber hinaus haben wir keinen Beweis dafür, dass GI nicht mit polylogarithmischem Nichtdeterminismus gelöst werden kann.

Siehe diesen verwandten Beitrag .

Dieser Beitrag zur CS-Theorie von @Salamon zeigt, dass wir nicht einmal wissen, ob GI mit einem Quadratwurzel-gebundenen Nichtdeterminismus oder gar einem polylogarithmischen Nichtdeterminismus entschieden werden kann.

Mohammad Al-Turkistany
quelle

Ich denke jedoch, dass viele Leute vermuten, dass GI in P. ist

Thomas

@ Thomas Babai hat in seiner Arbeit darauf hingewiesen, dass er gegen diese Vermutung ist.

Mohammad Al-Turkistany

Bist du dir so sicher, dass Babais Algorithmus nicht in ?

β P

$\beta P$

Joshua Grochow

@ MohammadAl-Turkistany Ironischerweise stammt die Frage zu MO, die Sie zitieren (sowohl in Ihrer Antwort als auch in Ihrem Kommentar), vom OP selbst vor 10 Monaten und hat (bis heute) keine Antwort. Ich bin mir nicht sicher, inwieweit dies Ihrer Argumentation Glauben schenkt - es impliziert nur, dass "Wir haben keinen Beweis dafür, dass GI in auf das in MathOverflow verwiesen wird " bestenfalls.

β P

$\beta P$

Clement C.

@JoshuaGrochow Ja, der Kommentar ist spezifischer (unter Hinweis auf den spezifischen Teil des Abschlusses). Aber die Antwort bezieht sich nur auf die Frage zu MO als einen starken Hinweis auf die Behauptung, dass es keinen Beweis gibt - was für mich kreisförmig klingt.

Clement C.