Holy crud, you're supposed to know this stuff going in to a course on complexity theory?
A Course on Complexity Theory « Gödel’s Lost Letter and P=NP.
[Update:]{style="color: #ff0000;"} Ah, I read it wrong -- when he said "What they should know," he meant at the end of the course, not coming in. Too bad in a way, because I was thinking "If these are the prerequisites, the coursework must be fracking research-grade."