Apr 09, 2020  
Rensselaer Catalog 2008-2009 
    
Rensselaer Catalog 2008-2009 [Archived Catalog]

Add to Portfolio

CSCI 6050 - Computability and Complexity


This course discusses modern concepts of computability and computational complexity theories. The Church-Turing thesis; variations of Turing Machines; Algorithms; Decidability; The Halting Problem; Reducibility; The Recursion Theorem; The Concept of Information; Time and Space Complexity; Intractability; NP-completeness and Cook’s theorem.

Prerequisites/Corequisites: Prerequisite: CSCI 2400 or equivalent.

When Offered: Fall term annually.



Credit Hours: 3



Add to Portfolio