Computational Complexity - Fall 1999

The notions of "computation" and "efficient computation" are among the fundamental notions in computer science, if not the most fundamental notions. Complexity theory defines these notions and classifies the computational problems according to their computational hardness, that is, their "complexity."

Homework and Exams:

1. Exercise 1, due November 9 (not on-line).
2. Exercise 2, due November 23.
3. Exercise 3, due December 7.
4. Exercise 4, due December 21.
5. Exercise 5, due January 4, 2000.
6. Exercise 6, due January 30, 2000.
7. Final Test
8. Final Test - Moed B

Syllabus:

1. Undecidability.
   • Turing machines and the Church thesis.
   • The halting problem is undecidable.
   • Rice's theorem and other undecidable problems.
2. Time and Space Complexity.
   • Space complexity and the relation between deterministic and non-deterministic complexity classes (Savitch's and Immerman-Szelepcsenyi's Theorems).
   • Time and space hierarchies and the existence of gaps (Borodin's Theorem).
3. Complexity classes. We will cover some of subjects below:
   • The P vs. NP question. NP-completeness of SAT and other problems.
   • Efficient reductions. Problems complete for NL, P, and PSPACE.
   • Boolean circuits and the class P/poly. Parallel computation and the class NC.
   • Probabilistic algorithms and Probabilistic complexity classes. The classes RP, BPP, and RL.
   • Counting problems and the class #P.
   • Interactive proof systems. The class IP and its equivalence to PSPACE.
   • Approximation schemes and hardness of approximation. The PCP characterization of NP.
   • Zero-Knowledge proofs; application in cryptography.

Lectures:

1. Introduction.
2. Definition of Turing Machines and Recursive languages
3. Church Thesis: Equivalence of TMs, Multi-tape TMS, non-deterministic TMs, and RAMS.
4. L_ACCEPT is undecidable.
5. More undecidable languages, Reductions.
6. Tiling is undecidable.
7. Rice Theorem, Definition of time and space classes.
8. Relations between time and space classes, linear speed-up.
9. Simulation of space-bounded non-deterministic TMs: Savitch's and Immerman-Szelepcsenyi's Theorems.
10. Time and space hierarchies.
11. Borodin's Gap theorem and transaltions lemmas.
12. Definitions of P and NP.
13. On NP-completeness.
14. SAT is NP-complete.
15. More NP-complete laguages.
16. Self Reducibility, Unary laguages are not NP complete.
17. coNP, PSPACE, TQBF is PSPACE complete.
18. NL, log space reduction,
19. CON is NL complete, Radomized algorithms.
20. Schwartz-Zippel Algorithm. Checking if a number is pseudo-prime.
21. Rabin algorithms for testing primality. The class RP.
22. The class BPP.
23. Approximation Algorithms -- Vertex Cover and set-cover.
24. PCP and hardness of approximation.
25. More approximation Algorithms -- Coloring 3-colorable graphs and Knapsack.
26. Cryptograph and Complexity

Grades:

Pre-requirements:

Books:

1. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
2. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
3. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations.
4. M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to NP-completeness. 1979.

Information:

Complexity courses on-line:

1. Introduction to Complexity Theory, by Oded Goldreich in the Weizmann Institute.
2. Advanced Complexity Theory, by Dan Spielman in MIT.
3. Complexity of Computation, by Eric Allender in Rutgers.