Theory of Computation

CS41001, Autumn 2022, LTP: 3-1-0

Class Slots	MON: 12:00-12:55; TUE: 10:00-11:55; THUR: 08:00-08:55
Venue	Section 1: NC243 Section 2: NC341

Instructors	Section 1: Somindu Chaya Ramanna Section 2: Dr. Sudeshna Kolay
Teaching assistants	Aniket Deroy, Tutan Nama, Nandini Jalan, Rajdeep Das, Rohan Meena

Notices and Announcements

Syllabus for Mid-Sem: Everything up to and including Godel's Incompleteness Theorem
Class Test 1 on 5 September 2022 (Monday) from 6:15 PM to 7:15 PM at CSE- 107,108,119,120.
Extra class (tutorial) on Saturday, 27 August 2022 from 10 AM to 11:30 AM at CSE 106
Class on 22 August 2022 (Monday) cancelled.
For registration approval requests via ERP, we have finalised the approval based on CGPA and the year of joining the institute. Please note that that CS21004 is a prerequisite for this course and we will not waive this prerequisite for anybody. No further requests will be considered.
Classes start on the 2nd of August, 2022. Odd roll numbered students have been allotted to Section 1 and the rest to Section 2.

Prerequisites

CS21004 Formal Languages and Automata Theory. (Here is a recap of what you learnt in this course.)

Syllabus

Theory of Computability
- Notion of computation, models of computation, Turing machines and their variants, equivalence, universal Turing machines and diagonalisation
- Decidable and undecidable languages, examples
- Reduction, Rice's theorem
- Undecidable problems about CFL's, Griebach's theorem, Post's correspondence problem (ref: 1,3,5)
- Recursive function theory: Turing computable functions, $S_{mn}$-theorem, recursion theorem and applications (ref: 3,5 and miscellaneous exercises 129-132 in 1), quines and self-reference
- Gödel's Imcompleteness Theorem (ref: 1)
- Other formalisms: Type-0 Grammars, Equivalence to Turing Machines, Chomsky Hierarchy (ref: 3)
Complexity Theory
- Modelling efficient computation
- Complexity classes: P, NP, EXP, R
- NP-hardness, NP-completeness, Cook-Levin Theorem, review of some NP-complete problems (ref: 2,8)
- Space complexity: PSPACE, NPSPACE, PSPACE-completeness, L, NL, NL-Completeness
- Hierarchy Theorems, Ladner's Theorem , Relativisation and limits of diagonalisation
- Polynomial hierarchy: classes $\Sigma_i^p$, $\Pi_i^p$, PH, alternating Turing machines, defining PH via oracle machines, time space trade-offs for SAT (ref: 2)
- Randomized computation: probabilistic Turing machines, examples; Classes RP, coRP, ZPP, BPP, randomised reductions; Error reduction, BPP is in PH

References

Automata and Computability by Dexter Kozen. (main text)

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

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

Introduction to Computability by Fred C. Hennie.

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

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

Computational Complexity by C. H. Papadimitriou.

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

Evaluation Plan (Tentative)

The evaluation for this course will be based on

2 Tests (20% of total credit)
Mid Semester Examination (30% of total credit)
End Semester Examination (50% of total credit)

Tutorials

Tutorial 1 Recursive and R.E. Sets, (Un)Decidability, Rice’s Theorem

Tutorial 2 Undecidable Problems about CFLs, PCP

Tutorial 2 Recursive Function Theory

Tutorial 4 Incompleteness Theorem, Type-0 Grammars

Tests/Exams

Class Test 1

Mid-Sem Exam

Policy on Plagiarism

Academic integrity is expected of all the students. Ideally, you should work on the assignments consulting only the material we share with you. You are required to properly mention/cite anything else you look at. Any student found to have submitted plagiarised solutions will be penalised heavily. Repeated violators of our policy will be deregistered from the course.

Possibly Useful Links

Courses:

Blogs:

In Theory by Luca Trevisan
Gödel's lost letter and P=NP by Richard Lipton
Shtetl-Optimized by Scott Aaronson

Complexity Zoo: a compilation of all existing complexity classes; the pdf version

General/Expository Articles:

Gödel, Hilbert and Brouwer
Hibert, Gödel and Turing
Hibert's Program Then and Now
Computability and Complexity by Jon Kleinberg and Christos Papadimitriou
Complexity Theory by Eric W. Allender, Michael C. Loui and Kenneth W. Regan
Complexity Theory - A Survey by Oded Goldreich
Complexity Theory - A Survey by Oded Goldreich and Avi Wigderson
The History and Status of the P vs. NP Question by Michael Sipser