CSC463H1: Computational Complexity and Computability


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.


CSC363H1/​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: 
Breadth Requirements: 
The Physical and Mathematical Universes (5)