CS 464Computational Complexity Theory
- Faculty
- Mathematics
- Offered
- Winter
- Credit
- 0.5
- Last listed
- 1994–95
No longer offered. It’s in Waterloo’s scanned calendars from 1989–90 to 1994–95 (before that, 1976–77 to 1987–88 used the number for Computability and Recursive Function Theory); the 1995–96 to 2023–24 calendars are on ucalendar.
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. Prereq: CS 360 and fourth-year standing
As printed in the 1989–90 to 1994–95 calendars, read by OCR; the scanned page is the original. Later calendars (1995–96 on) aren’t on uwloo.
Discussed on r/uwaterloo
One post or comment in 1 thread mentions CS 464, 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 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?”
Check it elsewhere
- Undergraduate Calendar, 1995–96If it ran past 1994–95, on ucalendar
- Course outlinesSyllabi from past terms (UW login)
- UW FlowStudent ratings and reviews
- WClassesPast sections back to 2004, and who taught them
In the scanned calendars
How it read in each calendar from 1976–77 to 1994–95, newest first. The text is OCR of the scanned pages; years whose wording matches are shown once, from the clearest scan. Each year links to its page on uwloo and to that page of the scanned PDF.
1989–90 to 1994–95 6 calendars
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. Prereq: CS 360 and fourth-year standing
Offered Winter · 3 class hours a week · 0.5 credit
Not in the 1988–89 calendar.
1976–77 to 1987–88 11 calendars
Another title: Computability and Recursive Function Theory, probably a different course under the same number (or a misread scan).
Models of the computational process as reflected by computers, linguistic systems, functional specifications, transformational systems, formal logic, etc. Equivalence of these models. Computational complexity for specific models and abstractions fitting all models. Formal reducibilities between computational problems, and the complexity of these reducibilities.
Prereq: CS 360 and fourth-year standing
Offered Winter · 3 class hours a week · 0.5 credit