Jul 14, 2025  
Rensselaer Catalog 2024-2025 
    
Rensselaer Catalog 2024-2025 [Archived Catalog]

Add to Portfolio (opens a new window)

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



Add to Portfolio (opens a new window)