Jul 18, 2024  
Rensselaer Catalog 2015-2016 
Rensselaer Catalog 2015-2016 [Archived Catalog]

Add to Portfolio (opens a new window)

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. Students cannot receive credit for both CSCI 4050 and CSCI 6050.

Prerequisites/Corequisites: Prerequisite: CSCI 2300 or equivalent.

When Offered: Fall term annually.

Cross Listed: CSCI 4050.

Credit Hours: 3

Add to Portfolio (opens a new window)