Sep 22, 2020  
Rensselaer Catalog 2008-2009 
Rensselaer Catalog 2008-2009 [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.

Prerequisites/Corequisites: Prerequisite: CSCI 2400.

When Offered: Fall term annually.

Credit Hours: 4

Add to Portfolio (opens a new window)