Monday, September 25, 2017

Day 14

Defined quantified Boolean formula and showed that TQBF, the set of true quantified Boolean formula, is PSPACE-complete.

Assignment 1 has been graded. Average score is 62. Solutions are posted to the resources section of the T-Square site. Assignment 2 will be handed out Wednesday.


  • Alternation by Chandra, Kozen and Stockmeyer. This is the paper that showed the equivalence of alternating polynomial time and PSPACE and my other relationships.
  • Nice write-up of proof that TQBF is PSPACE-complete via Joan Feigenbaum.