uwloo

CS 764Computational Complexity

Units
0.50
Level
Graduate
Faculty
Mathematics
Subject
Computer Science

CS 764 as listed in the Fall 2024 Graduate Calendar. The main page has the current version, when it runs, and seats.

Further exposure to the classification of problems based on their computational requirements and to mathematical tools designed to explore the structural consequences of such classifications. Topics include relativization, alternation, provably intractable problems, feasible parallel computation; fixed-parameter tractability and the W-hierarchy; Kolmogorov complexity, including algorithmic and algorithmic prefix complexity and their applications.

Prerequisites

None listed.

Antirequisites

  • Not completed nor concurrently enrolled in any of the following:
    • CS664 - Computational Complexity Theory (0.50)

Leads to

No course lists it as a requisite.

Check it elsewhere for Fall 2024

Calendar versions

Graduate Calendar

Older Graduate Calendars

In 42 terms, Fall 2006 to Winter 2024