Academic Calendar 2022-2023

Search Results

CISC 462 Computability and Complexity

CISC 462  Computability and Complexity  Units: 3.00  

Turing machines and other models of computability such as µ-recursive functions and random-access machines. Undecidability. Recursive and recursively enumerable sets. Church-Turing thesis. Resource-bounded complexity. Complexity comparisons among computational models. Reductions. Complete problems for complexity classes.

Learning Hours: 120 (36 Lecture, 84 Private Study)  
Requirements: Prerequisite Registration in a School of Computing Plan and a minimum grade of a C- (obtained in any term) or a 'Pass' (obtained in Winter 2020) in CISC 223. Recommended CISC 365.  
Offering Faculty: Faculty of Arts and Science