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: 
Exclusion: 

CSC363H1/​CSCC63H3, CSC365H1. NOTE: Students not enrolled in the Computer Science Major or Specialist program at the UTSG, UTM, or UTSC 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)