CMPS130: Overview of complexity classes, Part 4
C. Seshadhri · 9:59
PSPACE contains both NP and coNP because polynomial space can be reused to brute-force every polynomial-length certificate, and complementation does not increase space the way it does for time. The lecture places this...