Complexity Theory  

Course Objectives

At the end of the course, students will

• explain models of computation, resources (time and space), algorithms, computability, and complexity,
• learn randomized computation and complexity; logical characterizations, incompleteness and approximability, and
• understand circuit complexity, lower bounds; parallel computation and complexity; counting problems and interactive proofs.

Course Description

Turing machines: standard TM, computability of TM, techniques of TMs construction, Church’s hypothesis; computability (introduction to recursive function theory; primitive and partial recursive functions, recursive and recursively enumerable languages, Turing computable); undecidability (Turing decidable and Turing acceptable, undecidable problems); computational complexity (basics of algorithm analysis: Big O-notation, polynomial time and space; nondeterministic polynomial time; P vs NP, polynomial time reductions and NP-complete problems: Cook’s theorem).

Course Content

1. Turing Machines (TMs)
2. Computability
3. Undecidability
4. Computational Complexity