CS 664Computational Complexity Theory

Units: 0.50
Level: Graduate
Faculty: Mathematics
Subject: Computer Science

When it runs

Ran in 0 of the last 7 terms. Winter 2027: not on the schedule. Spring 2027: schedule not out yet.

The classification of problems according to the computational resources required for their solution, with emphasis on properties of feasible computations rather than on specific algorithms. Topics include: time and space complexity, tractable and intractable problems, computation using randomness, parallel computation.

Prerequisites

None listed.

Antirequisites

None listed.

Leads to

No course lists it as a requisite.

Discussed on r/uwaterloo

2 posts and comments in 2 threads mention CS 664, April 2019 to December 2024. Quoted word for word, newest first; each reply sits under the post and the comment that started its branch. Search r/uwaterloo for newer posts.

Winter 2021

Jan 25, 2021 Is CS 664 / 764 computational complexity no longer being offered? 4 points, 1 comment

u/standardtrickyness1: “Is CS 664 / 764 computational complexity no longer being offered?”

View on Reddit Remove this

Winter 2019

Apr 8, 2019 What happened to CS464/664 5 points, 6 comments

u/Dabestfujiyoshi: “I was looking into more courses on computational complexity because it seems like a really interesting topic, but the last course website is from 2002. Does it still exist? Where else can I get my fix?”

View on Reddit Remove this

Check it elsewhere for Fall 2026

Graduate Calendar, Fall 2026The official entry
Requirements for Fall 2026Waterloo’s requisite checker
Schedule of Classes, Fall 2026Instructors, rooms, live seats
Quest Class SearchWhere you enrol
Course outlinesSyllabi from past terms (UW login)
UW FlowStudent ratings and reviews
WClassesPast sections back to 2004, and who taught them

Calendar versions

Graduate Calendar

Older Graduate Calendars

In 42 terms, Fall 2006 to Winter 2024