Basic Information

Course overview

The course is to expose the attendee to the importance, history and progress of the study the limits of computation, its connection to various concepts that they have already seen in a basic "theory of computation" course. Then the course aims to motivate and expose to the fundamental understanding of "computation under resource constraints" - most often called computational complexity theory.

Course Syllabus

• Turing Machines:
  • Decision problems v/s Output machines, Determinism and Non-determinism
  • Designing Turing Machines for various problems
  • Recursive, Recursively Enumerable and Co-Recursively Enumerable Languages
  • Equivalent Models : Multi-tapes, Two way infinite, PDA with 2 stacks, Counter Automata
  • Universal Turing Machines: Diagonolization Technique, Undecidability of Halting Problem, Rice's Theorems
  • Other undecidable problems via reductions : Variants of Halting Problem, Tiling ...
  • Oracle Turing Machines : Arithematic Hierarchy
  • Turing Equivalent Models : λ calculus, Type 0 Grammars, (Non) Primitive Recursion
• Complexity Theory :
  • Time and Space as resource, Various Space and Time complexity classes
  • Time and Space Hierarchy Theorems, Relationship between Time and Space complexity classes
  • P and NP : NP completeness, Cook-Levin Theorem, complexity class NP ∩ CoNP, Padding arguments : Ladner's Theorem, Relativization, NP = P implies NEXP = EXP
  • Space complexity : Savitch's Theorem, Zimmerman-Szelepcsenyi Theorem, PSPACE and Quantified Boolean Formulas
  • Polynomial Hierarchy : Alternating Turing Machines, Oracle turing machines, Relationship with PSPACE
• Descriptive Complexity:
  • Introduction to various logics, Expressing properties in logic
  • Notion of a logic L capturing a complexity class C
  • Fagin's Theorem
• Introduction to some of the topics from the following list:
  • Circuit Model of Computation
  • Randomized computation
  • Interactive proofs
  • #P : counting complexity classes
  • PCP Theorem

Reference Text Books

• Automata and Computability by Dexter C. Kozen
• Computational Complexity : A modern Approach by Sanjeev Arora and Boaz Barak
• Theory of Computation by Dexter C. Kozen

Course Load

This is 12 credit course and has 4 lecture hours. This means that you should be expecting to put in 8 hours per week on the average to meet the expectations of the course which can be divided into 4-5 hours per week will be to learn/follow-up on the class material and the remaining 3-4 hours per week towards solving the assignments and/or practice problems.

Evaluation Scheme

• Mid Semester Exam (40%)
• Quiz/Assignment/Viva (20%) [To be decided based on class strength]
• End Semester Exam (40%)