13
$\begingroup$

I had done some search on this but I was not able to find an answer either way.

Huck answered it fully. Thanks :)

$\endgroup$
  • 1
    $\begingroup$ Can you move your "comment inside the question" to an actual comment. $\endgroup$ – Suresh Venkat Oct 12 '11 at 22:56
  • $\begingroup$ @Suresh, I do not think there is enough room for it? I am not sure. $\endgroup$ – Tayfun Pay Oct 12 '11 at 22:59
  • 2
    $\begingroup$ Can you perhaps remove the "comment" part entirely? I do not think that it is appropriate. $\endgroup$ – Jukka Suomela Oct 12 '11 at 23:14
  • 1
    $\begingroup$ Put whatever you can and remove the rest. And post this in Huck's answer. It's not appropriate to insert an answer comment inside the original question $\endgroup$ – Suresh Venkat Oct 12 '11 at 23:29
26
$\begingroup$

Here's a simple argument that shows that QP is not known to be in PSPACE:

Assume $QP \subseteq PSPACE$. Then we have $P \subsetneq QP \subseteq PSPACE$, where the first inclusion is proper by the time hierarchy theorem.

This separates $P$ from $PSPACE$, which is not known to hold, so $QP \subseteq PSPACE$ must also not be known to hold.

Indeed we have that $PSPACE \subseteq QP \Rightarrow PSPACE \subsetneq EXP$, but $QP \nsubseteq PSPACE$ does not separate the two classes by the THT (as stated in the question).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.