This course is required for the Theory of Computation concentration.

This course is of interest to students wishing to deepen their understanding of the nature of problem complexity.

Prerequisites:  COMP 3602 or the former COMP 3719

Availability: This course is occasionally offered, but will not be available every academic year.

Course Objectives

This course is an in-depth look at the theory of algorithms and algorithm complexity from a structural point of view. The emphasis will be placed on complexity classes containing problems of practical relevance such as P, NP and the parallel class of problems NC.

Representative Workload

• Assignments 40%
• In-class Exams 20%
• Final Exam 40%

Representative Course Outline

• Review of the basic formal models of computation and complexity:
• Random access machines
• Turing machines
• Oracle machines
• Alternating Turing machines
• Combinational circuits model
• Uniform and nonuniform complexity measures
• resource bounded computations
• Complexity classes:
• Resource bounded reducibility:
• Turing-Cook
• Polynomial time
• Logarithmic space
• The classes NP, P, NC, PSPACE, LOGSPACE and their complements
• Problems complete and hard for a complexity class
• Relationships between complexity classes
• The polynomial time hierarchy:
• Randomized computations
• Randomized algorithms
• Randomized complexity classes
• Randomized sources

Page last updated May 24th 2021