Computational Complexity

1 credits · Undergraduate

An introduction to computational complexity theory: Turing machines and computability, (non)deterministic polynomial time (classes P and NP), space complexity (classes L, NL, PSPACE), reductions and completeness, parallel and randomized computation, Boolean circuits, Kolmogorov complexity. Prerequisite: Computer Science 230, 231, 232 or equivalent.