
0368.3168

Fall 2009 
Out 
Due 
Questions 
23/10 
9/11 

12/11  26/11  
19/11  3/12  
6/12  21/12  
21/12  4/1/2010  Ex. 5 
6/1  21/1  Ex. 6 
17/1  29/1  Ex. 7 
Lectures

Lectures: Monday 

Instructors

Muli
Safra Schreiber 319  6405371  Office hour:
Monday Grader: Tomer Levinboim 

Lecture notes on the web

Oded
Goldreich from Weizmann
(see also here) 

Textbooks

Main references:
Other textbooks:


Requirements 
Attendance, homework assignments 

Prerequisites 
Computational Models, Algorithms 

Other links 
A compendium
of NPcomplete problems and what's known about them. 
13.
The Polynomialtime Hierarchy and BPP
Week 
Date 
Class Topics 
1 

Complexity functions, definition and example of Turing Machine.
(L) 
1 

The classes P,NP,coNP are closed under concatination (T). 
2  26/10/09  Time and space classes, Cook Theorem. 
2  29/10/09  Cook and Levin reductions (T). 
3  2/11/09  NPcomplete problems, 2SAT and Max2SAT. 
3  5/11/09  NP comlete Unary languages, self reductions (T) 
4  9/11/09  Space Complexity (L) 
4  12/11/09  Time hierarchy, the padding argument, 3NAE and 3Colorability (T) 
5  16/11/09  Space complextiy (Cont.) 
5  19/11/09  2SAT is NLcomplete 