CIS 622 Computational Complexity

Spring 2008

• CRN: 35741
• Room: (NEW ROOM!) 200 Deschutes
• Times: Tuesday and Thursday, 12:00-1:20pm
• Instructor: Chris Wilson
• Contact Info: room 326 DES, 346-3412, cwilson@cs.uoregon.edu
• Office Hours: tba
• Text: Computational Complexity, by Christos Papadimitriou, Addison-Wesley, 1994.

Evaluation

This will be based on written homework, probably 5 or 6 such assignments. There will be no exams, but there will be at the end of the term a take-home test, more or less the same format as the assignments.

Potential Topics

• Turing machine model, §2.1-2.5
• Basic complexity classes, §7.1-7.2
• NP-completeness, §8.1-8.2
• More NP-complete problems, §9
• Polynomial hierarchy, §10 (skim), §17
• Polynomial space, §19
• Randomization and circuits §11 (especially §11.4)
• Parallel computation: NC and AC §13
• Log space computation §16 and §7.3
• Theorem 17.7 on parallel queries to NP
• Interactive protocols in §19.2
• First order and second order graph properties §5.1-2, §5.7, §8.3
• MAXSNP and nonappproximability §13.2-3
• Quantum computation: the articles by Fenner and Simon, available through this link

Lectures

• (Apr 1) introduction, complexity classes
• (Apr 3) discussion of NP
• (Apr 8) circuit sat and 3sat
• (Apr 10) three colorability
• (Apr 15) three dimensional matching, partition
• (Apr 17) finish partition, coNP
• (Apr 22) polynomial hierarchy, padding
• (Apr 24) no lecture
• (Apr 29) polynomial hierarchy and PSPACE
• (May 1) Karp-Lipton collapse
• (May 6) QBF is complete for PSPACE
• (May 8)

Assignments

• Assignment 1, due April 29.
• Assignment 2, due May 13.

Class Handouts

• fundamental behaviors of complexity classes
• definitions of the main reductions used in this class
• some discussion of an oracle

References

• Introduction to Automata Theory, Languages, and Computation, Hopcroft and Ullman, Addison-Wesley 1979
• Structural Complexity I. Balcazar, Diaz, and Gabarro, Springer-Verlag 1988
• Theory of Computational Complexity, Du and Ko, Wiley 2000
• Computers and Intractability, Garey and Johnson, Freeman 1979
• Handbook of Theoretical Computer Science: Volume A, Algorithms and Complexity, van Leeuwen (ed.), MIT Press 1990. Especially useful for this class is §14 "The complexity of finite functions" by Boppana and Sipser.

Comments and Announcements

• Some excellent course notes for a similar class at MIT.
• You are welcome to drop by my office outside official office hours.
• Check out the Complexity Zoo.