Office of the Registrar
Campus Address
Hanover, NH
03755-3529
Phone: (603) 646-xxxx
Fax: (603) 646-xxxx
Email: reg@Dartmouth.EDU

Organization, Regulations, and Courses 2024-25

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.