Scott Aaronson’s mini-course at UFF, 2nd lecture

quantum Rio

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s