CSE6115
Computational Complexity
Fall 2012

The best way to contact me is probably by email. Please use your cs account when sending me email, and start your subject line with "[6115]". Send messages in plain text, without attachments.

Announcements

• (Sep 7) Some students have contacted me asking if the class times can be rescheduled so that they can attend. Note that you can still join the course in the second week, because we have only had a one-hour class on Sep 5. I plan to reschedule so that there are two 90-minute meetings per week. If you are interested in taking the course, please send me email by Sep 8 telling me (a) what times (Monday to Friday, 9am-6:30pm) you absolutely cannot attend the course, (b) which times you would prefer and (c) whether you would definitely take the course if it was scheduled when you could attend. I will try to settle the meeting times on Sep 9 and post them here.
• (Sep 7) I just realized that the orientation for new grad students conflicts with today's class, so I am cancelling the class so that students can attend the orientation sessions.

Course Overview

We'll look at models of computers (e.g. Turing machines) and see how they are used to measure the resources (time, space and others) required to solve problems. If we pick a model and a bound on one or more resources, we can define a complexity class (e.g. P, NP, NC) to be the set of problems that can be solved in that model with the given resources. These classes give us a systematic way of understanding how efficiently problems can be solved.

In studying complexity theory, we learn about techniques that can be used to design efficient algorithms. We also learn how to identify those problems for which efficient solutions do not exist or are unlikely to exist. Such information is useful, because it often suggests how to modify our approach when faced with an intractable problem: for example, we might look for approximate solutions instead of exact solutions, or try to solve a special case of the problem that is sufficient for our needs.

Much of the material will be taught from first principles, so there are no specific prerequisites. However, some background in algorithms and theoretical models of computing (e.g. Turing machines, finite automata) would be helpful, and you should be comfortable reading and writing mathematical proofs.

The exact set of topics to be covered will depend partly on students' interests and background, but here is a tentative list of topics:

• Models of computation: various types of Turing Machines, Random Access Machines
• Definitions of some basic complexity classes (LOGSPACE, P, NP, coNP, PSPACE) & relationships between them
• Time & space hierarchy theorems
• Reductions, NP-completeness
• An introduction to randomized computation
• Parallel computation (circuits, Parallel Random Access Machines, NC, P-completeness)
• Approximating solutions to intractable problems (if time permits)

Marking scheme:

Homework exercises	60%
Class presentation	10%
Paper report	10%
Paper presentation	20%

Most of the homework exercises will require you to write a proof. For the class presentation, you will have to read about some complexity class and report your findings (the definition of the class, why it is important, maybe one or two basic facts about it) to the class. For the paper presentation, you will be required to read a research paper on complexity theory and present the results to the class. More details about all of this work will be given in class.

Classes

• September 5: Introduction, why study complexity, how to measure complexity [AB 1.1]
• September 12: Formalizing problems, model of computation. Turing machines. [Sip 3.1] or [Pap 2.1]
• September 14: Lower bound on deciding palindromes [see notes]; simulating 2-way infinite tape with 1-way infinite tape.
• September 19: Simulating multitape with a single tape [Sip 3.2], Random Access Machines [Pap 2.6]
• September 21: Definition of TIME classes, basic properties [Sip 7.1-7.3]
• September 26: Non-deterministic Turing machines, simulating non-deterministic TM with a deterministic one [Sip 3.2]
• September 28: Reductions [Pap 8.1, Sip 7.4], verifiers [Sip 7.3].
• October 3: Facts about reductions, definition of NP-hard and NP-complete [Pap 8.1]
• October 5: NP-completeness of CLIQUE [Sip 7.4 or CLRS p.1003], SUBSET-SUM [Sip 7.5 or CLRS p.1014]
• October 10: NP-completeness of 3DM [GJ 3.1.2], 3COLOUR [CLRS, p.1019].
• October 12: Cook-Levin Theorem [Sip 7.4], NP-completeness of PARTITION and BIN-PACKING.
• October 17: Basic relationships between time and space classes [Pap 7.3]
• October 19: Savitch's Theorem [Pap 7.3, Sip 8.1]
• October 24: Immermann-Szelepscényi Theorem [Pap 7.3, Sipser 8.6] and 2SAT is in P [Pap].
• October 26: Definition and properties of logspace reductions. NL-complete problems: reachability, unreachability and 2SAT.
• November 7: Class presentations November 9: Diagonalization arguments November 14: Space hierarchy theorem November 16: CKTVAL is P-complete (and so is monotone CKTVAL) November 21: TQBF is PSPACE-complete November 23: GEOGRAPHY is PSPACE-complete, some examples of using randomization November 28: Randomized complexity classes BPP, RP, PP, ZPP November 30: December 3:

References

Books

• [AB] Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press, 2009. A draft of the book is available online.
• [BDG] José Luis Balcázar, Josep Diaz, Joaquim Gabarró. Structural Complexity I, 2nd ed. Springer, 1995. Nicely written, accessible introduction.
• [BC] Daniel Pierre Bovet and Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall, 1994.
• [DK] Ding-Zhu Du and Ker-I Ko. The Theory of Computational Complexity. Wiley-Interscience, 2000.
• [Gol] Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. Preliminary versions of this book are available from the author's website.
• [HS] Steven Homer and Alan L. Selman. Computability and Complexity Theory. Springer, 2001.
• [HU79] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation, 1st ed. Addison-Wesley, 1979.
• [Imm] Neil Immerman. Descriptive Complexity. Springer, 1999. Emphasizes connections to formal logic.
• [Pap] Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• [Sav] John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1998. Part III of this book discusses complexity theory.
• [Sip] Michael Sipser. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2013. Part III of this book discusses complexity theory.

Original Articles

• [CR73] S.A. Cook and R.A. Reckhow. Time bounded random access machines, J. of Computer and System Sciences, volume 7, pages 354-375, 1973.
• [HS65] J. Hartmanis and R.E. Stearns. On the computational complexity of algorithms, Trans. of the AMS, volume 117, pages 285-306, 1965.

Resources for Special Topics

• [ACG] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999. Associated with this book is the online Compendium of NP Optimization Problems, which is like a version of Garey and Johnson's appendix (with more emphasis on approximations).
• [CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, 3rd edition. MIT Press, 2009. Great general algorithms book, and it has a nice chapter on NP-completeness.
• [GJ] Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman, 1979. The bible of NP-completeness. Johnson has also published a sequence of columns (available here) that form a kind of sequel to the book.
• [GHR] Raymond Greenlaw, James Hoover, Walter L. Ruzzo. Limits to Parallel Computation: P-completeness Theory. Oxford University Press, 1995. (See their web site.)
• [SP] Uwe Schöning and Randall Pruim. Gems of Theoretical Computer Science. Springer, 1995. Each chapter presents a beautiful theorem from various fields of computer science (with a number from complexity theory).

More advanced complexity resources

• [Aar] Scott Aaronson (zookeeper). The Complexity Zoo. This wiki has information on hundreds of complexity classes. Its bibliography includes a huge number of papers on complexity theory.
• [HO] Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Springer, 2002. Arranges Theorems according to the techniques used to prove them.
• [RW] Steven Rudich and Avi Wigderson, eds. Computational Complexity Theory. AMS and Institute for Advanced Study, 2004. Lecture notes, starting from some basics, but moving quickly to more advanced topics.
• [Zim] Marius Zimand. Computational Complexity: A Quantitative Perspective. Elsevier, 2004. Focussed on questions of what fraction of problems in a class have certain properties.

Course Handouts

• Assignment 1
• Here is some Java code that you can use to help you test your solution to assignment 1. (It requires you to make some changes to the code.) Here is an example of a Turing machine in YUTMFF. It is the machine from the notes I handed out that decides palindromes.
• Assignment 2
• Assignment 3
• Assignment 4
• Assignment 5
• Assignment 6
• Assignment 7

Updated November 23, 2012