CSCI 6050 - 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.

When Offered: Fall annually

Co-Listed: CSCI 4050

Graded: Y

Credit Hours: 3