# TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

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

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)