Place and Time
11:00-12:30 MW
201 DMP
Instructor
Anne Condon
Office: X539 CS
Phone: 822-8175
Office Hours:
3:00 - 4:00 Tuesdays
(or by appointment)
Resources
Computational Complexity
by C. H. Papadimitriou
Addison-Wesley, 1994
Available in the reading room
Computational Complexity
by S. Arora and B. Barak, Cambridge University Press, 2009
Draft available on-line
Contains links to on-line graduate notes
Godel's Lost Letter and P=NP
Lipton's blog
|
Course Schedule
| Date |
Resources |
| Wed, Sep 8 |
Welcome!
Topic: Turing Machines
Slides, Turing machine handout
Reading:
Arora and Barak Sections 1.1, 1.2.
Be able to write down TM definitions and
definitions of time bounded language acceptance, function computation,
time constructibility from memory. Understand statements and proofs
of Claims in Section 1.2.2 (robustness).
|
|
| Mon, Sep 13 |
Topic: Turing Machines continued
Slides, Homework 1
Reading:
Arora and Barak Sections 1.3,1.4
Be able to describe what is a universal Turing machine,
define the Halting Problem and prove that it is uncomputable, write down definition of the class P.
Understand statement of Hennie and Stearn's theorem and the
proof of the relaxed variant given on p 22.
|
| Wed, Sep 15 |
Topic: P and NP, nondeterministic TMs, reductions
Sample in-class exercise.
Slides
Reading:
Arora and Barak Sections 1.5,2.1,2.2
Be able to define the classes P and NP, a
polynomial-time (Karp) reduction and what it means for a language to
be NP-complete or NP-hard. Understand how reductions are used to
establish NP-completeness results.
|
|
| Mon, Sep 20 |
Topic: The Cook-Levin Theorem, more reductions
Slides, Cook-Levin Theorem handout
Reading:
Arora and Barak Sections 2.2, 2.3,2.4
Be able to define what is a nondeterministic TM (NTM), what it means
for a NTM to accept a language, and the definition of NP in terms of
NTMs. Understand the statement and proof of the Cook-Levin
theorem. Develop more skills at doing polynomial-time reductions.
|
| Wed, Sep 22 |
Topic: co-NP, EXP, NEXP
Slides
See also
David Johnson's 2007 NP-completeness Column
In-class exercise.
Reading:
Arora and Barak Sections 2.5,2.6
Be able to define the classes co-NP, EXP, and NEXP, describe some complete
problems in these classes, and problems in NP &cap co-NP that are not known
to be in P.
|
|
| Mon, Sep 27 |
Topic: Time Hierarchy Theorems, Oracle TMs
Slides, Time Hierarchy Theorem handout
Reading:
Arora and Barak Sections 3.1,3.4,3.5
Be able to state the deterministic Time Hierarchy Theorem and Ladner's
Theorem. Understand the proof of the deterministic Time Hierarchy Theorem. Know what an Oracle TM is.
Student presentation: Robert Tseng on NP-hard problems pertaining to
robustness of sensor networks
|
| Wed, Sep 29 |
Topic: Oracle TMs and Limits of Diagonalization; Space Bounded TMs
Slides, Homework 2
Reading:
Arora and Barak Sections 3.5, 4.1, 4.2
Understand the proof of the Baker, Gill and Solovay Theorem. Be able to define
the space bounded complexity classes L, NL, PSPACE, NPSPACE and prove that
problems are NL-complete.
|
|
| Mon, Oct 4 |
Topic: Immerman-Szelepscényi Theorem
Reading:
Arora and Barak Section 4.4
|
| Wed, Oct 6 |
Topic: PSPACE-completeness, Savitch's Theorem
Guest lecture by Joel Friedman
Reading:
Arora and Barak Section 4.3
|
|
| Mon, Oct 11 |
Holiday - Canadian Thanksgiving
|
| Wed, Oct 13 |
Topic: The Polynomial Time Hierarchy, Alternating TMs
Slides
Reading:
Arora and Barak Sections 5.1,5.2, 5.2
Be able to define the polynomial time hierarchy and give some examples
of problems that are complete for levels of the hierarchy. Be able to
show that if NP=P then the polynomial time hierarchy collapses. Be
able to define the polynomial time hierarchy, and PSPACE, in terms of
polynomial-time alternating Turing machines.
|
|
| Mon, Oct 18 |
Topic: Randomized Computation
Slides
Reading:
Arora and Barak Sections 7.1,7.2,7.3,7.4
See also
Hastad's notes pages 90-91, for a nice presentation on polynomial
identity testing.
Be able to define the classes BPP, RP, co-RP and ZPP, describe
relationships among these classes, and describe an example of a problem
for which there is an efficient probabilistic algorithm but no known
deterministic algorithm.
Student presentation: Ryan Giuliani on the Complexity of GO.
|
| Wed, Oct 20 |
Topic: Randomized Computation continued
Slides, Homework 3
Reading:
Arora and Barak Sections 7.7,7.8
Understand the proofs of Sipser's theorem, that BPP is in the polynomial time
hierarchy and the statement of Adleman's theorem, that BPP is in P/poly.
|
|
| Mon, Oct 25 |
Topic: Randomized Computation continued
Slides, Space bounded probabilistic complexity classes handout
Reading:
Arora and Barak Sections 7.8, 7.10
Be able to define space bounded probabilistic complexity classes, show
RL=NL, and understand the proof that UPATH is in RLP.
Student presentation: Sam Bayless on SAT Solvers.
|
| Wed, Oct 27 |
Topic: Randomized Computation continued
Slides
Reading: Handout from last class
In-class exercise.
|
|
| Mon, Nov 1 |
Topic: Interactive Proof Systems
Slides,
IP = PSPACE, Part 1
Be able to define what is an interactive proof system, and understand arithmetization of
quantified Boolean formulas.
Reading project description
|
| Wed, Nov 3 |
Topic: Interactive Proofs continued
Slides,
IP = PSPACE, Part 2
|
|
| Mon, Nov 8 |
Topic: Approximation Algorithms
Slides,
Approximate Solutions to NP-hard Problems
Reading:
Arora and Barak Sections 11.1, 11.2
Be able to describe poly-time approximation algorithms with constant
factor approximation ratios for Max 3SAT, Vertex Cover and the
Traveling Salesman Problem (TSP) with triangle inequality, and be able
to explain why
the general TSP does not have such an algorithm unless P=NP.
|
| Wed, Nov 10 |
Topic: The PCP Theorem and Hardness of Approximation
Slides , Applications of the PCP Theorem to Hardness of Approximation
Understand the statement of the PCP theorem and be able to use the PCP
theorem to show that Max 3SAT and Max Clique do not have polynomial
time approximation algorithms with constant factor approximation ratios
unless NP=P.
|
|
| Mon, Nov 15 |
Topic: Gap-Preserving Reductions and Hardness of Approximation
Slides
Be able to use gap-preserving reductions to show hardness of approximation
results for Max Independent Set and other problems.
|
| Wed, Nov 17 |
Topic: Proof of a Weak Version of the PCP Theorem
Slides, Homework 4
Reading:
Arora and Barak Section 11.5
Understand the proof of the theorem that PCP(poly(n),1) contains NP.
Student presentation: Bader Al-Ahmad on Energy Efficient Task Partitioning and Scheduling.
Student presentation: Kyle d'Oliveira.
|
|
| Mon, Nov 22 |
Topic: Bio-molecular Programming
Slides
Understand how and why we might compute with DNA molecules, and what theoretical questions arise in this context.
Student presentation: Jimmy Kwa on Logical Characterization of NP.
Student presentation: Shabab Hossain.
|
| Wed, Nov 24 |
Topic: Bio-molecular Programming continued
Slides
Student presentation: David Chan.
Student presentation: Hajir Roozbehani on
Approximation Algorithms for Max Cut and Max 2SAT Using
Semidefinite Programming.
|
|
| Mon, Nov 29 |
Topic: Undirected ST-Connectivity is in Log-Space
Slides Part 1 ,
Slides Part 2 ,
Slides Part 3 ,
Slides Part 4
Project presentation: Bader Al-Ahmad, Kyle d'Oliveira, Jimmy Kwa, Robert Tseng.
|
| Wed, Dec 1 |
Topic: Undirected ST-Connectivity is in Log-Space continued
Project presentation: Sam Bayless, David Chan, Ryan Giuliani,
Shabab Hossain.
|
|
| Mon, Dec 10 |
Final Exam Information
|
|