Introduction to Complexity and Computability
This is a basic course on the theory of algorithms, computability and computational complexity. Roughly the first half of the course is devoted to the introduction to computability theory: Turing machines. Computable functions. Recursive and recursively enumerable languages and sets. Undecidable problems. The second half of the course is devoted to the study of space and time complexity classes: Equivalence of PSPACE and NPSPACE. Deterministic hierarchy theorems. Class NP. Polynomial reducibility among problems. Proofs of NP- completeness. Approximation algorithms and approximation schemes.
Edit resource New resource
6 rating 4 level 5 clarity 4 user's background
9 rating 3 level 7 clarity 3 user's background