Here’s my account of Scott’s second lecture, Scott was kind enough to point out some of the most glaring mistakes in an earlier version of these notes.
Resuming our discussion of the basic features of the main complexity classes, we start by noting that many problems are not even in NP, but “higher up” in the hierarchy, i.e. they are hard to solve and also hard to verify. As examples, one can generalize games of strategy for arbitrarily large board sizes, as is common with Go. It was shown that many such games of strategy are complete for PSPACE, which is the class of all decision problems solvable by a computer using polynomial-sized memory, with no restriction on time. So the inclusions we have are:
$latex P \subseteq NP \subseteq PSPACE \subseteq EXP$.
(where EXP is the class of problems solvable in exponential time). At least one of these inclusions…
View original post 1,984 more words