Computational Complexity - Fall 2000/2001

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."

Final Exams:

Homework :

1. Exercise 1, due 26.11.00 (ps file) (word file)
2. Exercise 2, due 10.12.00 (ps file) (word file)
3. Exercise 3, due 25.12.00 (ps file) (word file)
4. Exercise 4, due 07.01.01 (ps file) (word file)
5. Exercise 5, due 21.01.01 (ps file) (word file)
6. Exercise 6, due 12.02.01 (ps file) (word file)

Syllabus:

1. Undecidability.
   • Turing machines and the Church thesis.
   • The halting problem is undecidable.
   • Rice's theorem and other undecidable problems.
2. The P vs. NP question. NP-completeness of SAT and other problems.
3. 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.
4. Complexity classes. We will cover some of subjects below:
   • 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.

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:

Some on-line complexity courses and links:

1. Last year's course (including tests).
2. Technion's homework booklet of the Computability course.
3. Complexity Theory, Eyal Kushilevitz, Technion.
4. Introduction to Complexity Theory, by Oded Goldreich in the Weizmann Institute.
5. Advanced Complexity Theory, by Dan Spielman in MIT.
6. Complexity of Computation, by Eric Allender in Rutgers.
7. Hardness of Approximations. By S. Arora and C. Lund. In Approximation Algorithms for NP-hard Problems, Dorit Hochbaum, Ed. PWS Publishing , 1996. (Online version in Sanjeev Arora's homepage)-->