What is the Totally Quantified Boolean Formula (TQBF) problem?

Here we show that the totally quantified boolean formula (TQBF) problem is PSPACE-complete. This is very similar to the Cook-Levin theorem as well as Savitch's theorem, but now we want to make sure that the formula only has polynomial size. The trick is to utilize the "for all" quantifier to encode the recursive calls into one call.
Easy Theory Website: www.easytheory...
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶SEND ME THEORY QUESTIONS◀
[e-mail]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.