Apr 25, 2019  
Rensselaer Catalog 2017-2018 
    
Rensselaer Catalog 2017-2018 [Archived Catalog]

[Add to Portfolio]

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: Prerequisite: CSCI 2300.

When Offered: Fall term annually.



Cross Listed: CSCI 6050.

Credit Hours: 4



[Add to Portfolio]