Within the class there were two versions of a given test; however, these two versions were just problem permutations of each other. The results above are all for the first of these two permutations. The two classes each had different tests which were variants of each other, testing the same learning outcomes.

LO1 (Learning Outcome 1) -- Exhibit a simulation of one machine model with another. For instance, a Turing machine by a RAM.

LO2 -- Give a minimal classification of the complexity of a computational problem as being in one of the class L, NL, P, P/poly, NP, coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable.

LO3 -- Show the completeness of a complete problem for each of these classes.

LO4 -- Know properties of the randomized classes RP, BPP.

LO5 -- Know conditions under which various of these hierarchies might collapse.

LO6 -- Be able to explain interactive proof characterizations of classes like PSPACE.

LO7 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits or switching lemma techniques.

LO8 -- Exhibit a relativized separation (oracle result) of complexity classes for standard classes such as P and NP.

N/A -- Important material covered in the course but not directly related to a specific learning outcome.