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

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

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

<p>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).</p>

CC BY-SA 3.0
2011-10-12T22:25:13.270Z
2011-10-12T22:31:32.323Z
2011-10-12T22:31:32.323Z
Huck Bennett
<p>I had done some search on this but I was not able to find an answer either way.<p>
Huck answered it fully. Thanks :) <p></p>

CC BY-SA 3.0
2011-10-12T22:56:24.137Z
Can you move your "comment inside the question" to an actual comment.
Suresh Venkat
CC BY-SA 3.0
2011-10-12T22:59:03.243Z
@Suresh, I do not think there is enough room for it? I am not sure.
Tayfun Pay
CC BY-SA 3.0
2011-10-12T23:14:56.587Z
Can you perhaps remove the "comment" part entirely? I do not think that it is appropriate.
Jukka Suomela
CC BY-SA 3.0
2011-10-12T23:29:44.020Z
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
Suresh Venkat
<cc.complexity-theory><complexity-classes><time-complexity><space-complexity>
Is Quasi-polynomial time in PSPACE?
Tayfun Pay
# Is Quasi-polynomial time in PSPACE?

(Asked by: username_0 on 2011-10-12)

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

Huck answered it fully. Thanks :)

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, space-complexity
> **Comments:**
> **username_1**: Can you move your "comment inside the question" to an actual comment.  
> **username_0**: @Suresh, I do not think there is enough room for it? I am not sure.  
> **username_2**: Can you perhaps remove the "comment" part entirely? I do not think that it is appropriate.  
> **username_1**: 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  

---

## 1 answers

### Answer by username_3 on 2011-10-12. Score: 28 | Accepted answer

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).


---

