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