CSCI-6050

Computability and Complexity

This course discusses modern concepts of computability and computational complexity theories. The Church-Turing thesis; variations of Turing Machines; Algorithms; Decidability; The Halting Problem; Reducibility; The Recursion Theorem; The Concept of Information; Time and Space Complexity; Intractability; NP-completeness and Cook’s theorem. Prerequisite: CSCI- 2400 or equivalent. Fall term annually.

3 credit hours