17642 Computational complexity | Spring 2004, L-T-P: 3-1-0, Credits: 4 |
| Schedule: | Wednesday | 5:30pm | -- | 7:30pm | (Lecture) |
| Thursday | 5:30pm | -- | 7:30pm | (Lecture/Tutorial) | |
| Venue: | CSE 302 | ||||
| First meeting: | Jan 5, 04 |
A course on formal languages and automata theory is a must for every registrant. Though I will make quick recaps of the working of Turing machines, lack of a good understanding of these divine machines is very undesirable.
A course on design and analysis of algorithms is the second prerequisite. Students should possess capabilities to analyze the time and space requirements of an algorithm.
1. Introduction Turing machines, equivalence of reasonable models of computation, non-determinism, algorithms, decision versus optimization problems, reduction between problems.
[Download notes in pdf or ps.gz format.]2. Time complexity The complexity classes P, NP, Co-NP and Exp, completeness for NP, Cook's theorem, some well-known NP-complete problems, classes FP, FNP, TFNP and FNP-Complete, approximation algorithms.
[Download summary in pdf or ps.gz format.]
[Download solutions of exercises in pdf or ps.gz format.]3. Space complexity Classes PSPACE, NSPACE and PSPACE-complete, Savitch's theorem, logarithmic space, classes PolyL, L, NL, Co-NL and NL-complete.
[Download summary in pdf or ps.gz format.]
[Download solutions of exercises in pdf or ps.gz format.]4. Intractability Space and time hierarchy, EXPSPACE-completeness, alternating Turing machines and the polynomial hierarchy, relativization and oracle Turing Machines.
[Download summary in pdf or ps.gz format.]
[Download solutions of exercises in pdf or ps.gz format.]5. Randomized computation Classes RP, ZPP, PP and BPP.
[Download summary in pdf or ps.gz format.]
[Download solutions of exercises in pdf or ps.gz format.]6. Parallel computation Circuit complexity, classes NC and RNC, P-completeness.
[Download summary in pdf or ps.gz format.]
[Download solutions of exercises in pdf or ps.gz format.]7. Cryptography One-way functions, public-key cryptography, interactive protocols.
| [ Moret ] | Bernard M E Moret, The Theory of Computation, Addison-Wesley, 1998. [Webpage for the book] |
| [ Papa ] | Christos H Papadimitriou, Computational complexity, Addison-Wesley, 1994. [Webpage of the author] |
| [ Sipser ] | Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company 1997. [Webpage for the book] |
Indian editions are available for [ Moret ] and [ Sipser ]. At least a dozen copies of [ Papa ] are available in the Central Library. Students can consult any of the above three books. I think [ Sipser ] is the easiest to follow (in this lot), though it covers a little less than our intended syllabus. [ Papa ] is the de facto standard on this subject, but is very terse and difficult for not-so-serious reading. I found [ Moret ] too verbose and having somewhat non-smooth English.
I will mostly follow [ Sipser ] with occassional detours to [ Papa ].
Date and time: February 22 2004 (Sunday) forenoon (9:00-11:00am) at Room No 108.
Questions: Download in pdf or ps.gz format.
Solutions: Download in pdf or ps.gz format.
Date and time: April 01 2004 (Thursday) 6:30-7:30pm at Room No 302.
Syllabus: Chapter 4: Intractability (and hierarchy theorems).
Questions: Download in pdf or ps.gz format.
Solutions: Download in pdf or ps.gz format.
Date and time: April 25 2004 (Sunday) forenoon (9:00-12:00am) at Room No 108.
Syllabus: Chapters 1--7 with greater emphasis on Chapters 4--7.
Questions: Download in pdf or ps.gz format.
Solutions: Download in pdf or ps.gz format.