CMPS130: Overview of complexity classes, Part 5
C. Seshadhri · 9:21
Savitch’s theorem collapses deterministic and nondeterministic polynomial space (PSPACE = NPSPACE), and the natural complete problem for that class is QBF: satisfiability of a Boolean formula under an arbitrary mix of...