PSPACE-complete problems are the hardest problems in PSPACE, and include determining properties of regular expressions, truth of quantified Boolean formulas, and puzzles and games. Solutions to these problems can be used to solve any other problem in PSPACE in polynomial time.

A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.