References
[CLR] Thomas H. Cormen, Charles E. Leiserson and
Ronald L. Rivest,
Introduction to Algorithms, The MIT Press,
1990.
[Sip] Michael
Sipser, Introduction to the Theory of Computation,
PWS
Publishing Company, 1997.
[PAP] Christos H. Papadimitriou, Computational Complexity,
[MR] Rajeev
Motwani, Prabhakar Raghavan, Randomized Algorithms
AddisonWesley
Publishing Company, 1995.
[V] Vijay V. Vazirani,
Approximation Algorithms. Springer.
1 
1.03.04 Oded 
Recitation: Complexity of functions. [CLR 24], [Sip 7.1] Turing Machines (example – palindromes). [PAP 2.12.3], Multiple tape T.M. vs. Single tape ones. [PAP 2.3],[Sip 3.2] (doesn’t include time analysis). 
1 
4.03.04 Amnon 
Time and Space complexity. [PAP 7.1] The class P. [PAP 2.6] 
2 
8.03.04 Oded 
Multiple tape – cont. stconnectivity –in SPACE(log^{2}n) – an explicit machine. [PAP 7.3], [Sip 8.1] 
2 
11.03.04 Amnon 
Composition of space bounded machines. stconnectivity –in SPACE(log^{2}n) – the more general framework. [PAP 7.3] Diagonalization and universal TM for Halt [PAP 3.12] and for complexity class separation  The Time and space hierarchies. [PAP 7.2] 
3 
15.04.04 Oded 
Nondeterministic TM – two possible definitions. NTIME. Coclasses. [PAP 2.7,7.1] Diagonalization and universal TM for Halt and for complexity class separation. [PAP 7.2], [Sip 9.1] Circuits [PAP 11.4] 
3 
18.03.04 Amnon 
Reductions, [PAP 8.1] STCONN
is NLcomplete [PAP 7.3,16.1], CVAL is
PComplete [PAP 8.2] . 
4 
22.03.04 Oded 
CVAL is PComplete [PAP 8.2] 
4 
25.03.04 Amnon 
NP. All guesses can be made at beginning. NP as a game between an all powerful prover and a polynomial time verifier. CSAT is NPComplete. SAT, 3SAT are NPComplete. [PAP 8.2,9.2] 2SAT is in P, in fact in coNL. [PAP 9.2] 
5 
29.03.04 Oded 
2SAT is in coNL. [PAP 9.2] 3Col is NPC assuming 3NAE is NPC. [PAP 9.3] 
 
 
Pessach Holiday. 
5 
15.04.04 Amnon 
Clique, IS, VC, SetCover are NPcomplete. [PAP 9.2,9.3] TQBF is PSPACEcomplete. [PAP 19.1] Sigma_2, Pi_2. 
6 
19.04.04 Oded 
Self reducibility of 3SAT: reducing the search to the decision problem by a polynomial Turing/Cook reduction. [PAP 10.3] Padding argument [PAP 20.1] applied to ex2 q6 [ans2] and to Savitch theorem. 
6 
22.04.04 Amnon 
PH; coNP; Oracle machines[PAP 14.3] ; Self reducibility. [PAP 10.3] PH in terms of oracles, Sigma_k=coPi_k , TQBFk is Sigma_k complete. [PAP 17.2] 
 
26.04.04 
Memorial day. 
7 
29.04.04 Amnon 
NL=coNL [PAP 7.3]. Parallel computation, [PAP 15.1] . sorting in parallel. 
7 
3.05.04 Oded 
Separating AvP from EXP Separating P from Time(2^{n}) Separating AvP from Time(2^{n}) [ans2] 
8 
6.04.04 Amnon 
NC [PAP 15.3]. NC in DSPACe(polylog(n)). Probabilistic computation [PAP 11.1,11.2]. 
8 
10.05.04 Oded 
4NAE is NPC, 3NAE is NPC. PSPACE = NPSPACE revisited. Pratt's Theorem. 
9 
13.05.04 Amnon 

9 


10 


10 


11 


11 


12 


12 


13 


13 


14 


14 

