MWF 2:30-3:20, Hollister 312
Dexter: by appointment. Please contact Kelly.
Swamy: T 11-12, F 4-5. One of these may change.
Textbooks
Nothing is required, but Rogers and Garey/Johnson are classic texts and are highly recommended. The newer texts by Papadimitriou and Hemaspaandra/Ogihara are also excellent.
- C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- Lane A. Hemaspaandra and Mitsunori Ogihara, The Complexity Theory
Companion, Springer, 1998.
- M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- J. E. Hopcroft and J. D. Ullman.
Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
- H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.
These titles are on reserve in the Engineering library, Carpenter Hall.
Handouts
All handouts, articles, homework sets, etc. will be available on the web in pdf or html format. It is your responsibility to check often for new postings. For viewing pdf files, we recommend Adobe Reader, available free of charge. 
There will be biweekly homework sets consisting of 3-5 problems, due by 4pm on the due date. You may collaborate on homework. If you collaborate, pass in one copy of your solutions with the names of all collaborators. Acknowledge all sources, including others in the class from whom you obtained ideas. Late homework will not be accepted without a good excuse. Assignments and solutions will be posted on the web.
There will be two 72-hour takehome exams, open book and notes. No collaboration is allowed on the exams.
Approximate weights: Homework 50%, exams 25% each.
Familiarity with the content of CS481 and (CS482 or CS681) is assumed. In particular, we will assume knowledge of:
- discrete mathematical structures, including graphs, trees, dags
- O( ) and o( ) notation
- finite automata, regular expressions, pushdown automata, context-free languages
- Turing machines, computability, undecidability, diagonalization
- NP-completeness and polynomial-time reducibility.
Entries in italics will be covered as time permits.
- basic models of computation; determinism, nondeterminism, alternation
- complexity; space, time hierarchies
- complexity classes; reducibility; completeness
- Savitch's theorem; Immerman/Szelepcsényi theorem
- logspace; NC; P-hierarchy
- alternating Turing machines; QBF; games; logical theories
- oracles and relativization; sparse sets; Mahaney's theorem
- Kolmogorov complexity; probabilistic complexity classes; pseudorandomness
- interactive proofs; IP = PSPACE; zero-knowledge
- PCP; approximation
- nonelementary complexity; omega-automata; S1S, SnS; Safra's construction; mu-calculus
- general recursive functions; Kleene T-predicate; valcomps
- general reducibility; r.e. completeness; Church's thesis
- Gödel numbering; universal and s-m-n theorems; acceptable programming systems; combinatorial completeness; Rogers' isomorphism theorem; Rice's theorem
- self-reference; recursion theorem, paradoxical combinator, Gödel's incompleteness theorem
- productive, creative, simple, immune sets
- arithmetic hierarchy; T-, m-degrees
- priority arguments; Friedberg-Muchnik theorem; Ladner's theorem
- recursive trees; recursive ordinals; inductive definability; Pi-1-1 and analytic hierarchy; hyperelementary sets; IND programs; fairness; Harel's theorem.