Dec 07, 2025  
2020-2021 University Catalog 
    
Catalog Navigation
  Catalog Home
  General Information
  Undergraduate University Core
  Disability Resources
  Academic Regulations & Student Conduct
  What’s New
  Undergraduate & Graduate Programs
  Undergraduate Certificates
  Undergraduate Minors
  Major Change (CODO) Requirements
  Undergraduate
  College of Agriculture
  College of Education
  College of Engineering
  College of Health and Human Sciences
  College of Liberal Arts
  School of Management
  College of Pharmacy
  Polytechnic Institute
  College of Science
  College of Veterinary Medicine
  Exploratory Studies
  School of Information Studies
  Honors College
  Office of the Provost
  Polytechnic Statewide
  Articulation Agreements/Transfer Single Articulation Programs
  Graduate
  Graduate Studies
  Combined Degree Programs (Purdue undergrad/grad)
  Joint and Dual Degrees (agreements involving an international University)
  Professional
  College of Pharmacy - Professional
  College of Veterinary Medicine - Professional
  My Portfolio
HELP
2020-2021 University Catalog [ARCHIVED CATALOG]

Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Add to Portfolio (opens a new window)

CS 58400 - Theory Of Computation And Computational Complexity

Credit Hours: 3.00. The theory of general purpose programming systems. Recursive and partial-recursive functions; recursive and recursively enumerable sets. The Church-Turing thesis. The recursion theorem, Rogers’ translation theorem, Rice’s undecidability theorem. The general theory of computational complexity: there are no general solutions to natural optimization problems. Complexity for specific models of computation: the polynomial complexity classes P, NP, and PSPACE; NP-hard and PSPACE-hard problems, inherently exponential problems. Typically offered Spring.Credits: 3.00


Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Add to Portfolio (opens a new window)