- Defining TM's, Time-Hierarchy Theorem. NL=coNL. Savitch's theorem.
- Cooks Theorem, some NPC reductions. Mahaney's theorem, PH, Karp-Lipton theorem.
- If GI is NPC then PH collapses. (This will use PH, Karp-Lipton. Will also need hash functions, AM protocol for GIbar.)
- If PARITYSAT is in P then SAT is in R. (This will use some of the machiney devoloped for GI.)
- Everything in PH is \le_T^p #SAT. (Toda's theorem.)
- If CLIQUE can be approximated then P=NP. (STATE PCP, give proof of some easier cases, but do not proof the full theorem or even try.)
Other topics that would be reasonable to cover: Baker-Gill-Solovay Oracle, Hard vs Random stuff, PARITY not in constant depth, and CLIQUE not in Monotone P. Not doing BGS-oracle since I'm not doing enough proofs that relativize in the first place. Not doing Hard vs Random since its a bit hard and a bit random for this level of course. Not doing Circuit Stuff since that does not fit in that well with these topics (concrete vs. abstract complexity). Any of these points are debatable.
I'll be giving out my own notes. My experience is that using other peoples notes does not work, and others using mine does not work. My notes work for students taking my course, who see my lectures, and who have access to me. But they would not be good for anybody else.