Home PageHome Page
Rensselaer Polytechnic Institute (RPI) * Why not change the world?
Welcome to Rensselaer Polytechnic Institute
Home About RPI Academics & Research Student Life Admission News & Information
*
*
Home > Academics & Research > Courses > CSCI > CSCI-4050
Academics
Faculty
Undergraduate Majors and Degrees
Graduate Programs and Degrees
Interdisciplinary Programs
Educational Programs and Resources
Education for Working Professionals
Rensselaer Research Libraries
Academic & Research Computing
Catalog
Academic Calendar
*
Research Centers
Rensselaer Faculty
Research Platforms & Resources
Research Priorities
Undergraduate Research Program
Office of the Vice President for Research
*
*
* * *

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. Prerequisite: CSCI-2400. Fall term annually.

4 credit hours
* *
* *
*
* RPI Home Feedback Form Privacy Policy Media Policy Copyright Notice *
*
Rensselaer Polytechnic Institute (RPI), 110 8th St., Troy, NY 12180. (518) 276-6000
RPI Copyright © 1996–2005 Rensselaer Polytechnic Institute. All rights reserved worldwide.
Why not change the world?(SM) is a service mark of Rensselaer Polytechnic Institute.