Computational Complexity - Fall 2003/2004

Dr. Amos Beimel

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." In this course we will cover the basics of complexity theory.

Announcements:

Syllabus:

  1. Decidability and undecidability.
  2. The P vs. NP question. NP-completeness of SAT and other problems.
  3. Time and Space Complexity.
  4. Complexity classes. We will cover some of subjects below:

Lectures:

Num. Topic Date Handouts,
exercises
1 Introduction. 29.10.03  
2 Definition of Turing Machines and Recursive languages. 4.11.03  
3 ACCEPT is undecidable. 5.11.03  
4 More undecidable languages, Reductions. 11.11.03
Ex 1 (pdf file), (word file)
5 Definitions of P and NP. 12.11.03  
6 NP-completeness. 18.11.03  
7 SAT is NP-complete. 19.11.03  
8 More NP-complete languages. 25.11.03 Ex. 2 (pdf file), (word file)
9 Colorability is NP-complete.
Self-Reducibility. Unary language not NP-hard.
26.11.03  
10 Approximation Algorithms: Vertex Cover, Weighted Vertex Cover, Set-Cover 2.12.03  
11 More Approximation Algorithms: Metric Traveling Salesman, knapsack. 3.12.03  
12 Hardness of Approximation. 9.12.03  
13 Non-deterministic TM. Time-bounded classes. 10.12.03 Ex. 3
(pdf file), (word file)
14 Space-bounded classes. 16.12.03  
15 Simulation of space-bounded non-deterministic TMs: Savitch's and Immerman-Szelepcsenyi's Theorems. 17.12.03  
16 Time and space hierarchies. 23.12.03  
17 Linear Speed-up Theorem.
Translations lemmas
24.12.03 Ex 4 (pdf file) (word file). Due date 7.1.04.
18 DL vs. NL. NL-completeness. 30.12.03  
19 P-completeness. 31.12.03  
20 Circuit complexity. 6.1.04  
21 Parallel computation - the class NC 7.1.04 Ex 5 (pdf file) (word file). Due date 21.1.04.
22 Randomized algorithms. 13.1.04  
23 Randomized complexity classes: RP and BPP. 14.1.04  
24 Randomized log-space (RL). 20.1.04  
25 Cryptography and Complexity 21.1.04  
26 Example questions for the Exam 14.2.04  

Grades:

Final exam, 80%. Students MUST PASS the exam to pass the course.
Homework assignments, 20%. There will be about 6 homework assignments.

Pre-requirements:

The course is a mandatory graduate students. Good third year undergraduate students (average 85 and above) who are interested in theoretical computer science are invited to join.
Prerequisite Course: Design of algorithms.

Books:

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

Information:

Lectures hours: Tuesday 16:00-18:00, Building 90, Room 226,
Wednesday 15:00-17:00, Building 90, Room 137.
Reception hours: Wednesday 17-19, Building 58 (Math and CS), Room 205.
E-mail: beimel at cs.bgu.ac.il
Phone: 647 7858

Exams from Previous Years:

Fall 2002-2003: Moed A (pdf file) (word file),
Fall 2001-2002: Moed A (ps file) (word file),
Fall 2000-2001: Moed A (ps file) (word file), Moed B (ps file) (word file)
Fall 1999-2000: Moed A (ps file), Moed B (ps file)

Some on-line complexity courses and links:

  1. Home pages of the course from previous years: 1999, 2000, 2001, 2002.
  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 Madhu Sudan 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)