CS 664Computational Complexity Theory
- Units
- 0.50
- Level
- Graduate
- Faculty
- Mathematics
- Subject
- Computer Science
CS 664 as listed in the Spring 2025 Graduate Calendar. The main page has the current version, when it runs, and seats.
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.
Check it elsewhere for Spring 2025
- Graduate Calendar, Spring 2025The archived entry
- Requirements for Spring 2025Waterloo’s requisite checker
- 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
- Fall 2006
- Winter 2007
- Spring 2007
- Fall 2007
- Winter 2008
- Spring 2008
- Fall 2008
- Winter 2009
- Spring 2009
- Fall 2009
- Winter 2010
- Spring 2010
- Fall 2010
- Winter 2011
- Spring 2011
- Fall 2011
- Winter 2012
- Spring 2012
- Fall 2012
- Winter 2013
- Spring 2013
- Fall 2013
- Winter 2014
- Spring 2014
- Fall 2014
- Winter 2015
- Spring 2015
- Fall 2015
- Winter 2016
- Winter 2020
- Spring 2020
- Fall 2020
- Winter 2021
- Spring 2021
- Fall 2021
- Winter 2022
- Spring 2022
- Fall 2022
- Winter 2023
- Spring 2023
- Fall 2023
- Winter 2024
- All archived calendars