Ist die quasi-polynomiale Zeit in PSPACE?

Ich hatte einige Nachforschungen angestellt, konnte aber in keiner Weise eine Antwort finden.

Huck antwortete voll und ganz. Vielen Dank :)

cc.complexity-theory complexity-classes time-complexity space-complexity Tayfun Pay
quelle

Können Sie Ihren "Kommentar innerhalb der Frage" in einen tatsächlichen Kommentar verschieben?

Suresh Venkat

@Suresh, ich glaube nicht, dass es genug Platz dafür gibt? Ich bin mir nicht sicher.

Tayfun Pay

Kannst du vielleicht den "Kommentar" -Teil komplett entfernen? Ich halte das nicht für angebracht.

Jukka Suomela

Legen Sie alles, was Sie können, und entfernen Sie den Rest. Und poste dies in Hucks Antwort. Es ist nicht angebracht, einen Antwortkommentar in die ursprüngliche Frage einzufügen

Suresh Venkat

Antworten:

Hier ist ein einfaches Argument, das zeigt, dass QP in PSPACE nicht bekannt ist:

Angenommen, . Dann haben wir , wobei die erste Einbeziehung nach dem Zeithierarchiesatz korrekt ist. $QP \subseteq PSPACE$ $P \subsetneq QP \subseteq PSPACE$

Dies trennt von , von dem nicht bekannt ist, dass es gilt. muss daher ebenfalls nicht bekannt sein, dass es gilt. $P$ $PSPACE$ $QP \subseteq PSPACE$

In der Tat haben wir , aber trennt die beiden Klassen nicht durch die THT (wie in der Frage angegeben). $PSPACE \subseteq QP \Rightarrow PSPACE \subsetneq EXP$ $QP \nsubseteq PSPACE$

Huck Bennett
quelle