CS682 Spring 08 :: Theory of Computation :: Course Information

Instructor

MWF 2:30-3:20, Upson 111

Newsgroup

Textbooks

The main text for the course will be

• Dexter Kozen, Theory of Computation, Springer, 2006.

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

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/1
• HW2 W 2/13
• HW3 M 2/25
• HW4 F 3/7
• Prelim: any 72-hour period from F 3/7 to 4pm F 3/14
• Spring break M 3/17 - F 3/21
• HW5 F 3/28
• HW6 F 4/11
• HW7 M 4/21
• HW8 F 5/2
• Final: any 72-hour period from F 5/2 to 4pm M 5/12

Regarding the homework

• We encourage you to collaborate in small groups (3 or fewer).  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 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ⁿbⁿ | n ≥ 0}, not just aⁿbⁿ.
• 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 terminology and 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.