COSC 40 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.

The Timetable of Class Meetings contains the most up-to-date information about a course. It includes not only the meeting time and instructor, but also its official distributive and/or world culture designation. This information supersedes any information you may see elsewhere, to include what may appear in this ORC/Catalog or on a department/program website. Note that course attributes may change term to term therefore those in effect are those (only) during the term in which you enroll in the course.