$PH \subseteq PSPACE$.

In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space.

I am having a hard time understanding why this is true. I'll try to explain:

Let's take for example $L \in\Sigma_2$: by definition, $x \in L \Longleftrightarrow \exists y_1\forall y_2 : V(y_1,y_2)=1$. But finding such $y_1$ and checking it against all possible $y_2$s has to take more than polynomial space! The machine has to remember each $y_2$ that it tried in order to make sure that it indeed tried out all of the options, and the number of possible $y_2$s is exponential, which makes it exponential space.


1 Answer 1


No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, just remembering the last one is enough.


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.