Course Information

Staff

Instructor

Dexter Kozen
kozen@cs.cornell.edu
Upson 5143
255-9209

Teaching Assistant

Reba Schuller
ras51@cornell.edu
Upson 5142
255-1165

Administrator

Beth Howard
bhoward@cs.cornell.edu
Upson 5147
255-4188

Office Hours

By appointment. For an appointment with Dexter, please contact Beth. For an appointment with Reba, please contact Reba.

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. These titles are on reserve in the Engineering library, Carpenter Hall.

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.

Handouts

All handouts, articles, homework sets, etc. will be available on the web. Most of the notes are in postscript format, so you will need access to a postscript previewer such as ghostview or a postscript printer. Please let me know if you experience difficulties.

Homework sets and handouts will be posted periodically. It is your responsibility to check for new postings.

Public Newsgroup

I have asked CIT to delete the newsgroup for this course, since there has been no activity.

[ A public newsgroup cornell.class.cs682 has been created for technical discussions, questions, and announcements. Please feel free to use this group as you would any newsgroup or public bulletin board. Free-ranging technical discussions are especially encouraged. I will try to respond to questions posted to this group within one working day. ]

Homework and Exams

There will be biweekly homework sets consisting of 3-5 problems, due in class 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.

Prerequisites

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.

Approximate Syllabus

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.