Class Timings |
MON: 12:00-12:55; TUE: 10:00--11:55; THUR: 08:00-08:55 |

Venue |
TBD |

Instructors |
Sujoy Ghose and Sudeshna Kolay |

Teaching assistants |
Sarthak Chakraborty, Omar Eqbal, Arijit Kar, Saurav Likhar, Ayan Zunaid, Manad Mishra |

- Notion of computation, models of computation, revision of Turing machines
- Recursive function theory: Turing computable functions, $S_{mn}$-theorem, recursion theorem and applications (ref: 3,5 and miscellaneous exercises 129-132 in 1)
- Other formalisms: Type-0 Grammars, Equivalence to Turing Machines, Lambda Calculus (ref: 1,3)
- Decidable and undecidable languages, examples
- Reduction, Rice's theorem
- Undecidable problems about CFL's, Post's correspondence problem (ref: 1,3,5)
- Gödel's Imcompleteness Theorem (ref: 1)

- Modelling efficient computation
- Complexity classes: P, NP, EXP
- NP-hardness, NP-completeness, Cook-Levin Theorem, review of some NP-complete problems (ref: 2,8,9)
- Space complexity: PSPACE, NPSPACE, PSPACE-completeness, L, NL, NL-Completeness
- Hierarchy Theorems
- Polynomial hierarchy: classes $\Sigma_i^p$, $\Pi_i^p$, PH, alternating Turing machines, time space trade-offs for SAT (ref: 2)

2. Computational Complexity by S. Arora and B. Barak. (main text)

3. Introduction to Automata Theory, Languages and Computation by John E. Hopcroft and Jeffrey D. Ullman. (reference for some topics covered in class)

4. Introduction to Computability by Fred C. Hennie. (recursive function theory)

5. Introduction to the Theory of Computation by Michael Sipser. (reference for some topics covered in class)

6. Elements of the Theory of Computation by H. Lewis and C. Papadimitriou.

7. Computational Complexity by C. H. Papadimitriou.

8. Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson.

9. Algorithm Design by Jon Kleinberg and Eva Tardos.

There will be at least 4 take home assignments, of 10-15 marks.

There will be at least 4 timed quizzes, of 15-20 marks.

Lec 0 | FLAT recap | Book reference: Dexter Kozen |

1.09.2020 | Lecture slides | |

3.09.2020 | Same slides | |

8.09.2020 | Lecture slides | Book Reference: Dexter Kozen Ch. 28-29; Sipser Ch. 6.1 |

10.09.2020 | Lecture slides, Practice Prob. Soln. | Book Reference: Sipser, Hopcroft Ullman Motwani, Pages from Old version of Hopcroft Ullman |

14.09.2020 | Lecture slides | Book Reference: Dexter Kozen Ch. 36 |

15.09.2020 | Part 1 | Book Reference: Dexter Kozen Ch. 37 |

Part 2 (Lecture on Unrestricted Grammars and TMs, with problems and solutions) | Part 2 notes | |

21.09.2020 | Lecture (Lecture on Reductions and undecidability, with problems and solutions) | Lecture notes, Book Reference: Dexter Kozen Ch. 31-33 |

22.09.2020 | Lecture (Lecture on Rice's theorems, with problems and solutions) | Lecture notes, Book Reference: Dexter Kozen Ch. 34 |

28.09.2020 | Lecture slides | Book Reference: Hopcroft Ullman Motwani |

29.09.2020 | Lecture (Lecture on Undecidable problems about CFLs, with problems and solutions; also refer to the lecture called "Clarification" for VALCOMPS being CFL or regular) | Lecture notes, Book Reference: Dexter Kozen Ch. 35 |

5.10.2020 | Lecture slides | Book Reference: Dexter Kozen Ch. 38-39 |

8.10.2020 | Lecture slides | Book Reference: Arora Barak Ch. 1-2 |

12.10.2020 | Same slides and Lecture slides | Book Reference: Dexter Kozen Ch. 38-39, Kleinberg Tardos NP-hardness chapter |

13.10.2020 | Same slides, Practice problems | Book Reference: Kleinberg Tardos NP-hardness chapter |

19.10.2020 | Lecture slides | Book Reference: Arora Barak Ch. 3 |

20.10.2020 | Lecture slides | Book Reference: Arora Barak Ch. 4 |

22.10.2020 | Lecture slides, Practice problems | Book Reference: Arora Barak Ch. 4 |

22.10.2020 | Lecture slides, Practice problems | Book Reference: Arora Barak Ch. 5 |

Hibert, Gödel and Turing

Hibert's Program Then and Now