COSC 240 Computational Complexity

This course covers the basics of computational complexity, whose broad goal is to classify computational problems into classes based on their inherent resource requirements. Five key computational resources are studied: time, space, nondeterminism, randomness, and interaction. Key concepts studied include reductions, the polynomial hierarchy, Boolean circuits, pseudorandomness and one-way functions, probabilistic proof systems, and hardness of approximation.

Prerequisite

COSC 39 or equivalent. Students need to be familiar with the formalism of the Turing Machine and with the notion of NP-completeness.