Computational Complexity

COMPSCI 335

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.

Prerequisites

Prerequisite: Computer Science 230, 231D, or 232

Curriculum Codes
  • QC
  • QS
Typically Offered
Occasionally