COSC 4200 - Computability and Complexity

Credits: 3
Max Credit: 3

Introduction to theoretical study of computability and efficient computation. Finite-state and pushdown automata; turing machines and the Church-Turing thesis; undecidability, computational complexity; NP-completeness.

Prerequisite: COSC 3020.