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

Addison-Wesley Publishing Company, 1995.

[V]     Vijay V. Vazirani, Approximation Algorithms. Springer.

 

 

 

1

1.03.04

Oded

 

Recitation:

Complexity of functions. [CLR 2-4], [Sip 7.1]

Turing Machines (example – palindromes). [PAP 2.1-2.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.

s-t-connectivity –in SPACE(log2n) – an explicit machine. [PAP 7.3], [Sip 8.1]

 

2

11.03.04

Amnon

Composition of space bounded machines.

s-t-connectivity –in SPACE(log2n) – the more general framework. [PAP 7.3]

Diagonalization and universal TM for Halt [PAP 3.1-2]

and for complexity class separation -  The Time and space hierarchies. [PAP 7.2]

3

15.04.04

Oded

 

Non-deterministic TM – two possible definitions. NTIME. Co-classes. [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 NL-complete [PAP 7.3,16.1], CVAL is P-Complete [PAP 8.2] .

4

22.03.04

Oded

CVAL is P-Complete [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 NP-Complete. SAT, 3SAT are NP-Complete. [PAP 8.2,9.2]

2SAT is in P, in fact in co-NL. [PAP 9.2]

5

29.03.04

Oded

2-SAT is in co-NL. [PAP 9.2]

3-Col is NPC assuming 3-NAE is NPC. [PAP 9.3]

--

----

Pessach Holiday.

5

15.04.04

Amnon

Clique, IS, VC, SetCover are NP-complete. [PAP 9.2,9.3]

TQBF is PSPACE-complete. [PAP 19.1] Sigma_2, Pi_2.

6

19.04.04

Oded

Self reducibility of 3-SAT: 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; co-NP; Oracle machines[PAP 14.3] ; Self reducibility. [PAP 10.3]

PH in terms of oracles, Sigma_k=co-Pi_k , TQBF-k 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(2n)

Separating AvP from Time(2n) [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

4-NAE is NPC, 3-NAE is NPC.

PSPACE = NPSPACE revisited.

Pratt's Theorem.

9

13.05.04

Amnon

 

9

 

 

10

 

 

10

 

 

11

 

 

11

 

 

12

 

 

12

 

 

13

 

 

13

 

 

14

 

 

14