14
$\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$
4
  • 1
    $\begingroup$ Can you move your "comment inside the question" to an actual comment. $\endgroup$ Commented Oct 12, 2011 at 22:56
  • $\begingroup$ @Suresh, I do not think there is enough room for it? I am not sure. $\endgroup$
    – Tayfun Pay
    Commented Oct 12, 2011 at 22:59
  • 2
    $\begingroup$ Can you perhaps remove the "comment" part entirely? I do not think that it is appropriate. $\endgroup$ Commented Oct 12, 2011 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$ Commented Oct 12, 2011 at 23:29

1 Answer 1

28
$\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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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