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.

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, P, 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 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits.

LO7 -- 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.