So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The latter requires demonstrating an algorithm which computes the L in polynomial space. This is usually achieved by having recursive calls such that is re-used.

In TBQF proof, the equation $\phi_{i+1}(A,B)$= $\exists Z [\phi_{i+1}(A,Z) \land \phi_{i+1}(Z,B) ]$ ($Z$ is mid-point )is default recursive relation for computing TBQF truth. In any standard proof, it is said that $\phi_{i+1}(A,B)$ is computed two times and for $m$ nodes, this formula explodes hence, other recursive-relation should be used to bound.

However in Savitch's proof, the recursive relation is $Path(a,b,t)$ = $Path(a,mid,t-1)$ AND $Path(mid,b,t-1)$ accepts then ACCEPT. In proof, it is stated that this relation reuses-spaces.

My Question is Why in TBQF relation space explodes while in Path, it is reused? Both of these relations looks more or less same to me because both refers to i-1 instances and will need space to store them?.


1 Answer 1


In the proof of the $\textit{PSPACE-}$completeness of TQBF, we need to construct a formula of some specific type. The recursive midpoint algorithm is easy to implement (and Savitch's Theorem requires finding the $\textit{algorithm}$), while the same idea, if performed in a similar manner, results in an exponential formula (and the completeness proof requires the $\textit{formula}$).

More generally, suppose there's some language $\textit{L}$, an optimal algorithm $A$ deciding $L$, and the smallest formula (maybe quantified) $\varphi$, s.t. $\varphi(x) = 1 \Leftrightarrow x \in L$. For me, it's not very clear why $A\in \textit{PSPACE}$ would imply that $\varphi$ is small (I only see it as a consequence of the $\textit{PSPACE}-$completeness theorem)


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.