NP- and PSPACE-Completeness

We introduce NP-completeness. We prove the Cook-Levin Theorem. Using it we prove many natural problems are NP-complete, and using similar ideas show QBF is PSPACE complete, and then show several natural problems are PSPACE complete. We prove Savitch’s Theorem showing that NPSPACE=PSPACE. We finish by looking at advice classes, BPP and randomization.