CSCI 4050 - Computability and Complexity

This course discusses concepts of languages defined by formal grammars, Turing machines and rewriting systems, computability, Church-Turing thesis, decidable and undecidable problems, computational complexity, polynomial reducibility, NP-completeness, and Cook’s theorem.

Students cannot receive credit for both CSCI 4050 and CSCI 6050.

Prerequisites/Corequisites: CSCI 2300

Co-Listed: CSCI 6050

Graded: Y

Credit Hours: 4