CSC463H1: Computational Complexity and Computability

Hours

24L/12P

Introduction to the theory of computability: Turing machines and other models of computation, Church’s thesis, computable and noncomputable functions, recursive and recursively enumerable sets, many-one reductions. Introduction to complexity theory: P, NP, polynomial time reducibility, NP-completeness, self-reducibility, space complexity (L, NL, PSPACE and completeness for those classes), hierarchy theorems, and provably intractable problems.

Prerequisite
CSC236H1/CSC240H1/CSC236H5/CSCB36H3
Exclusion
CSC363H1/CSC363H5/CSCC63H3, CSC365H1. NOTE: Students not enrolled in the Computer Science Major or Specialist program at the FAS, UTM, or UTSC, or the Data Science Specialist at FAS, are limited to a maximum of three 300-/400-level CSC/ECE half-courses.
Distribution Requirements
Science
Breadth Requirements
The Physical and Mathematical Universes (5)