COMP 4742: Computational Complexity

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