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