Sign-in Links
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
Computing, Mathematics and Analytics – Specialization (Computing) – Bachelor of Computing (Honours)
...in Computer Science: CISC 422 ; CISC 462 ; CISC 465 ; CISC 466 ; CISC 467 ; MATH 401...
Computing, Mathematics and Analytics – Specialization (Computing) – Bachelor of Computing (Honours)
...in Computer Science: CISC 422; CISC 462; CISC 465; CISC 466; CISC 467; MATH 401...