MWF 2:30-3:20, Hollister 306
Dexter: by appointment. Please contact Kelly.
Zoya: by appointment. Please contact
Zoya.
Newsgroup
We have a course newsgroup, cornell.class.cs682. All course announcements will be posted
there; please check daily for new announcements. You may also use the newsgroup for technical discussions,
posting general questions about the homework, etc. The course staff will try to respond to
questions in a timely manner, or if you know the answer, feel free to post it yourself. Please avoid giving
away any hints on the homework though.
CMS
We are using the course management system, CMS. Kelly has entered everyone who preregistered,
but if you did not preregister, you are probably missing. Please login to
http://cms.csuglab.cornell.edu/ and check whether
you exist. There will be a list of courses you are registered for, and Com
S 682 should be one of them. If not, please send your full name and Cornell netid to
Kelly so she can register you.
You can check your grades and submit homework in CMS. There is a help page
with instructions.
Textbooks
The main text for the course will be
- Dexter Kozen, Theory of Computation, Springer, 2006.
This is essentially a collection of lecture notes and exercises from previous
versions of this course. Unfortunately, the book will not hit the shelves until
March 2006, so the publisher has kindly given us permission to distribute photocopies
of an abridged version to students enrolled in the course. These are
available free of charge from Kelly. However, to protect its copyright,
the publisher has insisted on some restrictions.
- The photocopies are available only to students enrolled in the course.
- The photocopies must be returned at the end of the semester.
- The photocopies may not be photocopied.
I ask you to comply with these restrictions. As an added incentive,
Springer has generously supplied us with coupons for 20% off the list price.
You will receive a coupon when you return the photocopied version to Kelly.
Other excellent sources:
- 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.
-
Ingo Wegener.
Complexity Theory:
Exploring the Limits
of Efficient Algorithms. Springer, 2005.
-
Steven Homer and Alan L. Selman.
Computability and Complexity Theory. Springer, 2001.
These titles are on reserve in the Engineering library, Carpenter Hall.
Handouts
All handouts other than homework and exams 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 the homework in small groups.
If you collaborate, submit one copy of your solutions with the names of all
collaborators. Acknowledge all sources, including others in the class from
whom you obtained ideas. Please type or write legibly and staple.
There will be a significant point deduction for late homework without a good
excuse. Assignments and solutions will be posted in CMS. Submit
hardcopy in class or to Kelly by 4pm on the due date, or a .pdf, .ps, .doc, or
.txt file in CMS. Do not submit Latex source.
There will be two 72-hour takehome exams, open book and notes. No
collaboration is allowed on the exams. Sign out the exam
with Kelly Patwell in 5147 Upson. Return the completed exam to Kelly
within 72 hours after signing it out (she must be there to record the time, do
not just slip it under the door), or submit it via CMS. If you wish to
submit your exam during non-business hours, you must submit it via CMS.
Graded homework and exams will be passed back in class, otherwise old homework
and exams will be available from Kelly.
Approximate weights: Homework 50%, exams 25% each. Note that the exams
comprise a much more significant portion of your grade than the homework.
Exam questions are of roughly the same level of difficulty as the homework
questions.
Due dates (subject to change):
HW1 F 2/3
HW2 W 2/15
HW3 M 2/27
HW4 F 3/10
Prelim: any 72-hour period from F 3/10 to 4pm F 3/17
Spring break M 3/20 - F 3/24
HW5 F 3/31
HW6 F 4/14
HW7 M 4/24
HW8 F 5/5
Final: any 72-hour period from F 5/5 to 4pm M 5/15
Regarding the homework:
- We encourage you to work in small groups.
It is more fun for you because you have others to bounce ideas off and you learn more,
and it is more fun for us because there is less to grade.
- You do not have to form CMS groups to work in groups. Only one person
in a group needs to submit the homework. We will transfer the grades to
the collaborators. Just make sure everyone's name is on it, and include
everyone's Cornell NetID too.
- The preferred interpretation of collaboration on the homework is
not "Dick does problem 1 and Jane does problem 2," but rather
"Dick and Jane do problem 1 and Dick and Jane do problem 2."
- If you submit hardcopy, staple!
- You are encouraged to type solutions. If you write by hand, please write
neatly and legibly.
Regarding proofs:
It is often difficult for beginning graduate students to get used to the
style and level of detail we would like to see. Many students, based on
experience from their undergraduate days, tend to be overly formal. Some
are careless in their use of mathematical notation. Some do not write in
complete English sentences, but pepper their proofs with arrows and
half-sentences and expect the reader to piece it together.
One of the goals of this course is to get you used to writing good proofs.
This is a good skill to cultivate, as you will soon be writing articles for
publication. Here are some rules of thumb to go by; please heed them well.
- Your arguments need not be overly formal, but must be logically correct
and convincing. The logical flow of your argument should be clear from
the presentation. Write in complete English sentences. Make sure
the reader knows which of your statements are assumptions, which are
conclusions, and how variables are quantified ("for all...", "there
exists..."). Justify all steps; the reader should not have to fill in
leaps of logic. Include intuitive motivation, but mark it clearly as
such.
- Always be on the lookout for ambiguities. Just because you know what
interpretation you intended does not mean the reader can decipher it.
Read through what you have written and imagine yourself a reader seeing it for
the first time.
- Use mathematical notation correctly. For example, if you are talking
about a set, use proper set notation like {a^n b^n | n >= 0}, not just a^n
b^n.
- Augment the proof with well-chosen examples and figures if they clarify
matters, but do not substitute them for the argument itself.
- Define all nonstandard notation.
- Avoid gratuitous formality. It does not make your argument any more
convincing. Indeed, more often than not, it is an annoyance to the
reader, who has to decode it. In particular, when giving algorithms, avoid
pseudo-code unless absolutely necessary. It is usually better to give a
high-level description of the algorithm in English. If you
must use pseudo-code, comment liberally, use descriptive variable names,
describe the purpose of each part, and state loop invariants. Never
give Turing machine transitions unless explicitly requested; it is almost
always below the level of detail that anyone wants to see.
- Keep solutions short and to the point. Omit irrelevancies and streams
of consciousness. Simplify as much
as possible. There are many ways to do this. Exploit
symmetry; in particular, if there are two cases that are similar or identical to
each other under some obvious modification, omit one without loss of generality.
The exercises we give you will rarely require more than a page. If you
find yourself writing pages and pages, you are probably on the wrong track.
On the other hand, students very often come up with simplifications of our
posted solutions. We spend a lot of time trying to find the simplest
solution possible, so if you come up with something simpler, then you are doing
well!
- If an argument is really straightforward, say so and omit it. This
includes proofs by induction; one can often get away with something like, "It is
easily shown by induction on the height of the tree that..." However,
please do not use this technique to try to bluff your way through a step you do
not understand.
Soon after each homework assignment is due, solutions will be posted. Please read
them, because it will give you a good idea of the style and level of detail we expect.
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.
The course is organized around a few fundamental themes. The exact coverage is subject to change. Topics below
will be covered as time permits; we will probably not have time to cover everything.
- 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
- complexity of logical theories
- 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.