CMPT 710 Computational Complexity
Spring 2009
Instructor: Gábor Tardos (tardos at cs.sfu.ca, office: TASC1 8227)
Solutions to last two assignments posted.
See me this week or in May to get your assignments back.
Finals grades entered.
Outline:
The main goal of Complexity Theory is to answer the question: What can be
efficiently computed given limited resources? This is a more "practical"
version of the main question of Computability Theory: What can be
computed? In this course, we will see a rich landscape of complexity
classes that are used to characterize problems according to the required
resources (such as time, space, randomness and parallelism). We will
discuss some known and (much more) conjectured relationships among these
classes,
obtaining a detailed map of the complexity world. Proving the correctness
of this map would involve solving some of the deepest open problems in
computer science, including the famous "P vs NP" question.
Schedule:
Classes: Monday 12:30-1:20, AQ5014, Wednesday 11:30-1:20, TASC2-8201
Office hour on Monday at 10:30-11:20 or even better if you email me for an appointment.
First class: Monday, January 7, 2009. Last class: Monday, April 6, 2009.
Textbook
We will not be following a textbook but the content of the course is covered
in the following books:
(recommended) László Lovász, Péter Gács: Computation Complexity,
Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Company,
Christos Papadimitriou: Computational Complexity, Addison-Wesley.
You may also find useful Valentine Kabenets's lecture notes from his 2007 course on the bottom of this course page.
Grading is based on
Homework assignments
Final
Homework assignments
See policy on collaboration.
There were six assignment throughout the semester. They are no longer available on this site.
Reminder of topics covered in class
January 5: Class canceled because of snow.
January 7: What is complexity: Tale about King Arthur, the wizard Merlin and the fifty knights of the round table (© László Lovász, László Babai). Formal introduction of strings (as encodings of problem instances) languages (as decision problems), Turing Machines, their input, computation, output and the time and space used by the computation. Undecidable languages exist (counting argument). Concrete example: the halting problem is undecidable.
January 12: More examples of undecidable languages. Components of the proof: diagonzlization and reduction.
January 14: Time and space complexity classes, hierarchy teorems, linear speedup theorems.
January 19: Extreme speedup theorem.
January 21: NP definition (wittnesses), polynomial time reduction, NP-completeness, Cook-Levin Theorem: 3SAT is NP-complete. Padding: L=P implies PSPACE=EXP.
January 26: Other NP-complete languages.
January 28: Nondeterministic Turing Machines, nondeterministic time and space complexity classes.
February 2: Savitch's Theorem: NSPACE(s(n)) is contained in DSPACE(s^2(n)) for functions s(n)>log n computable in O(s(n)) space.
February 4: s-t connectivity is NL-complete for logspace reduction. Immerman-Szelepcsényi Theorem: NL=co-NL.
February 9: Succinctly represented graphs. s-t connectivity for succinctly represented graphs is PSPACE-complete.
February 11: QBF (quantified Boolean formula) is PSPACE-complete. Boolean circuit evaluation is P-complete for logspace reduction. Search to decision reducibility for some problems in NP (including all NP-complete problems) and why it doesn't work for NEXP (nondeterministic exponential time).
February 16: Oracle Turing Machines.
February 18: Relativized worlds with P=NP and P≠NP.
February 23: Circuit complexity. Most of the n-variable Boolean functions require circuit-size Ω(2^n/n).
February 25: Furst-Saxe-Sipser theorem on PARITY not computable in constant depth, polynomial size circuits. See notes.
March 2: Randomization, one-sided error, two sided error, error-reduction.
March 4: Randomized algorithms: polynomial identity test, primality test based on Fermat's (little) theorem.
March 9: Randomization does not help with circuits: the same functions can be computed in polynomial size with and without randomization.
March 11: Randomization and NP: interactive and Arthur-Merlin proofs. Interactive proof for Graph-non-isomorphism.
March 16: Arithmetization: Interactive proof for #3SAT.
March 18: IP=PSPACE.
March 23: The PCP theorem (without proof) and some applications.
March 25: Class canceled.
March 30: Toward optimal inapproximability results.
April 1: Communication complexity (deterministic, nondeterministic, randomized).
April 6: Randomized communication complexity of inner product, connection between communication complexity and circuit depth.