|
May 11, 2024
|
|
|
|
CAS 705 / Computability and Complexity 3 unit(s)
Staff
Computability: Finite automata, Turing machines, and recursive functions. The Halting problem and the Church-Turing thesis. Complexity: Classes defined in terms of time, space, and circuits. The reachability method. The P vs. NP problem, Cook’s theorem, and NP-completeness. The Time and Space Hierarchy theorems. Randomized and parallel computations.
Add to Favourites (opens a new window)
|
|