||The class P and the class NP. Nondeterministic Turing machines, equivalent definition of NP.
NP-hardness. Example NP-complete problem. Statement of NP-completeness of SAT
|| Lecture notes (from 2014 offering)
Chap 1 of [AB], Sec 2.1, 2.2 and beginning of 2.3 of [AB]
Proof that SAT is NP-hard. (Check these notes for a proof of NP-completeness of SAT for a RAM model.)
Class coNP. NP and coNP are in EXP.
Deterministic time hierarchy theorem.
|| Chap 2 et 3.1 of [AB]
|| Space complexity. L, NL, PSPACE. Relation to time classes. TQBF is PSPACE complete.
|| Chap 4.1 and 4.2 of [AB]
|| Proof of PSPACE-completeness of TQBF. PSPACE = NPSPACE. NSPACE(S) in SPACE(S^2) (Savitch theorem).
Class NL, NL-hardness PATH is NL-complete.
Stated NL = coNL.
|| Sec 4.2 and 4.3 (space complexity) of [AB]
Proof NL = coNL. Oracle Turing machines. Statement of existence of oracles A,B with P^A=NP^A and P^B \neq NP^B
|| Chap 4 and Sec 3.4 of [AB]
Proof of existence of oracles A,B with P^A=NP^A and P^B \neq NP^B.
Polynomial hierarchy with alternating quantifiers and with oracle machines. If \Sigma_i = \Pi_i then the hierarchy collapses. Definition of polynomial hierarchy with oracles.
|| Sec 3.4, 5.1, 5.2, 5.5 of [AB]