Computational Complexity - Fall 2002/2003

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:

  1. 20.2.03 - The final grades are published. They were calculated according to the following formula: (test+6)*0.75+exercise*0.25.
  2. Grades of the exercises.
  3. 16.2.03 - The exam (ps), (word).
  4. 21.1.03 - An UPDATED collection of questions (to help you study for the exam). (ps file), (word file).
  5. 12.2.03 - Solution of Ex. 6 (ps), (pdf).
  6. 12.1.03 - Solution of Ex. 5 (ps), (pdf).
  7. 13.1.03 - Solution of Ex. 4 (ps), (pdf).
  8. 8.2.03 - Solution of Ex. 3 (ps), (pdf).
  9. 8.2.03 - Solution of Ex. 2 (ps), (pdf).
  10. 28.11.02 - Solution of Ex. 1 (ps), (pdf).
  11. 24.11.02 There was a mistake in question 1 in ex2. A corrected version can be found here: (ps file), (word file)
  12. 22.10.02 There will be only one test (no "moed b" exam).

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. 22.10.02 Announcement
2 Definition of Turing Machines and Recursive languages. 23.10.02  
3 L_ACCEPT is undecidable. 29.10.02  
4 More undecidable languages, Reductions. 30.10.01
Ex 1 (ps file), (word file)
5 Definitions of P and NP. 5.11.02  
6 NP-completeness. 6.11.02  
7 SAT is NP-complete. 12.11.02 Ex. 2 (ps file), (word file)
8 More NP-complete languages. 13.11.02  
9 Colorability is NP-complete.
Self-Reducibility. 		26.11.02 Ex 3 (ps file) (word file)
10 Unary language not NP-hard. 27.11.02  
11 Approximation Algorithms: Vertex Cover, Set-Cover, and Metric Traveling Salesman. 3.12.02  
12 Hardness of Approximation. 4.12.02  
13 Non-deterministic TM. Definition of time-bounded and space-bounded classes. 10.12.02 Ex. 4
(ps file), (word file)
14 Properties of space-bounded classes. 11.12.02  
15 Simulation of space-bounded non-deterministic TMs: Savitch's and Immerman-Szelepcsenyi's Theorems. 17.12.02  
16 Time and space hierarchies. 18.12.02  
17 Translations lemmas.
Non-deterministic Log space (NL) 		23.12.02 Ex 5 (ps file) (word file). Due date 7.1.03.
18 NL-completeness. 24.12.02  
19 P-completeness. 31.12.02  
20 P-completeness and circuit complexity. 1.1.03  
21 Parallel computation - the class NC 6.1.03 Ex 6 (ps file) (word file).
22 Randomized algorithms. 7.1.03  
23 Randomized complexity classes: RP and BPP. 14.1.03  
24 Cryptography and Complexity 15.1.03  
25 Example questions for the Exam 14.2.03  

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 14:00-16:00, Building 90, Room 145,
Wednesday 14:00-16:00, Building 90, Room 145.
Reception hours:Wednesday 16-18, Building 58 (Math and CS), Room 205.
E-mail: beimel at cs.bgu.ac.il
Phone: 647 7858

Exams from Previous Years:

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