COMP 352 Computability and Complexity

This course discusses the theoretical foundations of computing and the limits to computation itself. Topics include state machines and automata, general recursive functions, and their relationship to the Church-Turing thesis. The course may also survey decidable and undecidable problems, as well as “hard” (NP-complete) problems and what makes them hard.

Sub-field: THEORY