Computational Complexity - Fall 2001/2002

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:

3.2.02 - A lecture before the exam will be held on Wednesday 6.2.02 at 13:00 in room 201 building 58 (math and CS building). Please give me in advance questions for the lecture.
20.1.02 - A collection of questions (to help you study for the exam). (ps file), (word file).
20.1.02 - ex5 (ps file) (word file). Due date 4.2.02.

Final Exam:

Thursday, 7.2.02

Syllabus:

Decidability and undecidability.
- Turing machines and the Church thesis.
- The halting problem is undecidable.
- Rice's theorem and other undecidable problems.
The P vs. NP question. NP-completeness of SAT and other problems.
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.
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. PCP characterization of NP.
- Zero-Knowledge proofs; applications in cryptography.

Lectures:

Num.	Topic	Date	Handouts, exercises
1	Introduction.	23.10.01	Announcement
2	Definition of Turing Machines and Recursive languages.	24.10.01
3	Church Thesis: Equivalence of TMs, Multi-tape TMS, and non-deterministic TMs.	30.10.01	Ex. 1, due 14.11.01 (ps file), (word file)
4	L_ACCEPT is undecidable.	31.10.01
5	More undecidable languages, Languages not in RE.	4.12.01
6	Reductions and Rice's theorem.	5.12.01	Ex. 2, due 18.12.01 (ps file), (word file)
7	Definitions of P and NP.	11.12.01
8	NP and NP-completeness.	12.12.01
9	NP-complete languages.	17.12.01
10	SAT is NP-complete.	18.12.01	Ex. 3, due 1.1.02 (ps file), (word file)
11	More NP-complete languages.	19.12.01
12	SAT is self reducible. Unary language not NP-hard.	24.12.01	Algorithm (ps file), (word file)
13	Definition of time-bounded and space-bounded classes.	25.12.01
14	Properties space-bounded classes. Linear speed-up Theorem.	26.12.01
15	Simulation of space-bounded non-deterministic TMs: Savitch's and Immerman-Szelepcsenyi's Theorems.	1.1.02
16	Time and space hierarchies.	2.1.02	Ex. 4, due 15.1.02 (ps file), (word file)
17	Translations lemmas. Non-deterministic Log space (NL)	7.1.02
18	NL-completeness.	8.1.02
19	Randomized algorithms.	9.1.02
20	Randomized complexity classes: RP and BPP.	14.1.02
21	Randomized log-space (RL). Undirected connectivity is in RL.	15.1.02
22	Approximation Algorithms: Vertex Cover, Set-Cover, and Metric Traveling Salesman Problem.	16.1.02
23	Hardness of Approximation.	22.1.02	Ex. 5, due 4.2.02 (ps file), (word file)
24	Cryptography and Complexity	23.1.02
25	Example questions for the Exam	6.2.02

Grades:

Final exam, 70%. Students MUST PASS the exam to pass the course.
Homework assignments, 30%. 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:

M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations. Second Edition, 2001.
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 , Room ,
	Wednesday 14:00-16:00, Building, Room .
Reception hours:	Wednesday 12:00-14:00, 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:

Home pages of the course from previous years: 1999, 2000.
Technion's homework booklet of the Computability course.
Complexity Theory, Eyal Kushilevitz, Technion.
Introduction to Complexity Theory, by Oded Goldreich in the Weizmann Institute.
Advanced Complexity Theory, by Dan Spielman in MIT.
Complexity of Computation, by Eric Allender in Rutgers.
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)