# Is TQBF in CNF is still PSPACE-complete

TQBF(Totally Quantified Boolean Formula) is a PSPACE-complete question. I wonder that if it restricted to CNF is still PSPACE-complete. TQBF-CNF means that the part following the quantifier is a CNF.
I tried to prove that TQBF can be reduced to TQBF-CNF but failed as it need an exponential time to change a formula into CNF.
I would much appreciate an answer or an idea

Yes, it is still PSPACE-complete. Let $$Q_1 x_i \cdots Q_k x_k . \varphi(x_1,\dots,x_k)$$ be a TQBF problem, where each $$Q_i$$ is a quantifier. Apply the Tseytin transform to $$\varphi(x_1,\dots,x_k)$$ to get an equisatisfiable CNF formula $$\Psi(x_1,\dots,x_k,x_{k+1})$$, so that $$\varphi(x_1,\dots,x_k) \Leftrightarrow \exists x_{k+1} . \Psi(x_1,\dots,x_k,x_{k+1})$$. Then the original TQBF problem is equivalent to $$Q_1 x_1 \cdots Q_k x_k \exists x_{k+1} .\Psi(x_1,\dots,x_k,x_{k+1}),$$ which is an instance of TQBF-CNF. Therefore, any algorithm to solve TQBF-CNF can be used to solve TQBF.
As explained in Wikipedia, the size of $$\Psi$$ is polynomial in the size of $$\varphi$$. Note that $$x_{k+1}$$ might represent multiple variables. The number of added variables is also polynomial in the size of $$\varphi$$.
• Thanks for the answer! But I'm confused abut of the number of variables in $\Psi$, why do we need to add exactly one variable? In wikipedia, the example has the same number of variables after Tseytin transform. Commented May 4 at 5:11