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