COSC6115, Fall 2010
COSC6115
Computational Complexity
Fall 2010
Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Email: [my last name] @cse.yorku.ca
Telephone: (416) 7362100 ext. 33979
Facsimile: (416) 7365872
Lectures: Tuesdays and Thursdays from 11:30 to 13:00 in room 104 of Vanier College.
Office Hours: I will hold regular office hours on Tuesdays from 1:00 to 2:00 and Fridays from 11:00 to noon. If you cannot make it at those times, feel free to contact me to make an appointment at a different time. You can also try dropping by my office.
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
 (Nov 16) In question 1(a) of assignment 8, I meant to ask you to show that MONOTONE circuit SAT is not NPcomplete.
 (Oct 18) Since I will be attending the ACM regional programming contest on Oct 22, my office hour for that day is cancelled. You can come by my office on Thursday afternoon if you have questions.
 (Sep 30) Due to a departmental seminar and meeting, my office hour on Friday, October 1 has changed again: it will be at 10:30 a.m. instead of 11:00 a.m.
Course Overview
This course is intended to give graduate students a solid grasp of the fundamentals of complexity theory, which is an important part of the foundations of the entire field of computer science.
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, NPcompleteness
 An introduction to randomized computation
 Parallel computation (circuits, Parallel Random Access Machines, NC, Pcompleteness)
 Approximating solutions to intractable problems (if time permits)
You can look at the 6115 course web page from the last time it was offered to get an idea of what was covered then.
Marking scheme:
Homework exercises  70% 
Class presentation  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 14: Introduction, why study complexity, how to measure complexity [AB 1.1].

September 16: Turing Machine basics [AB 1.2] or [Pap 2.1].

September 21: Simulating 2way infinite tape with 1way infinite tape. Lower bound on time to decide palindromes using singletape TM. [Lecture notes on lower bound]

September 23: Multitape Turing machines. Definitions of TIME and SPACE complexity classes. Linear Speedup. [Pap 2.32.5]

September 28: Random Access Machines. Simulations between TMs and RAMs. [Pap 2.6]

September 30: Universal Turing machine. Diagonalization, undecidable problems.[AB 1.3, 1.4] or [Pap 3]
October 5: Time Hierarchy Theorem [Pap 7.2 or AB 3.1]

October 7: Nondeterministic Turing machines [ ], basic relationships between complexity classes [Pap 7.3]

October 19: Presentations of classes: PSPACE by Xiwen, APX by Shouzheng and Parity P by Joanna

October 21: Presentations of classes: RL by Elise and BPP by Calden. Also, Savitch's Theorem.

October 26: Savitch's Theorem. ImmermanSzelepsc&eacu;nyi Theorem. [Pap 7.3]

October 28: Reductions. [Pap 8.1]

November 2: Example reduction: Unreachability to 2SAT [Pap 16.1]. Completeness: definitions, basic properties [Pap 8.2].

November 4: NL algorithm for complement of 2SAT [Pap 9.2]. Reachability is NLcomplete (and so is 2SAT) [Pap 16.1].

November 9: Circuitvalue is Pcomplete. CircuitSAT is NPcomplete. [Pap 8.2]

November 11: NPcompleteness of SAT, 3SAT, 3DMatching [Pap 9.4 or GJ 3.1.2] and SubsetSum [CLRS, p.1014].

November 16: NPcompleteness of Clique [CLRS p.1003], Vertex Cover [CLRS p.1006], and 3Colourability [CLRS, p.1019].

November 18: NPcompleteness of Integer Programming. Randomization in algorithms.

November 23: Randomized complexity classes PP, BPP, RP, coRP, ZPP [Pap 11]

November 25: Randomized complexity classes (continued). Definition of Polynomial Hierarchy [Pap 16.2,17].

November 30: BPP contained in Sigma_2^P and Pi_2^P [Pap 17.2].

December 2: AL = P [Pap 16.2].

December 7: Class presentations. Calden (Yao's Principle), Elise (Tally Languages and Complexity Classes).

December 9: Class presentations. Xiwen (On Time vs Space), Shouzheng (A Hierarchy for Nondeterministic Time Complexity), Joanna (quantum computing, with Grover's algorithm).
References
Books

[AB] Sanjeev Arora and Boaz Barak.
Complexity Theory: A Modern Approach.
To be published by Cambridge University Press in 2009. In the meantime,
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] DingZhu Du and KerI Ko.
The Theory of Computational Complexity.
WileyInterscience, 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.
AddisonWesley, 1979.

[Imm] Neil Immerman.
Descriptive Complexity.
Springer, 1999.
Emphasizes connections to formal logic.

[Pap] Christos Papadimitriou.
Computational Complexity.
AddisonWesley, 1994.

[Sav] John E. Savage.
Models of Computation: Exploring the Power of Computing.
AddisonWesley, 1998.
Part III of this book discusses complexity theory.

[Sip] Michael Sipser.
Introduction to the Theory of Computation, 2nd edition.
Thomson, 2006.
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 354375, 1973.

[HS65] J. Hartmanis and R.E. Stearns. On the computational complexity of algorithms, Trans. of the AMS, volume 117, pages 285306, 1965.
Resources for Special Topics

[ACG] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. MarchettiSpaccamela 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, 2nd edition.
MIT Press, 2001.
Great general algorithms book, and it has a nice chapter on NPcompleteness.

[GJ] Michael R. Garey and David S. Johnson.
Computers and Intractability.
W. H. Freeman, 1979.
The bible of NPcompleteness.
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: Pcompleteness 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
Updated November 30, 2010