Go to Main Content

Purdue Self-Service



Catalog Entries


Spring 2019
Jun 30, 2022
Transparent Image
Information Select the Course Number to get further detail on the course. Select the desired Schedule Type to find available classes for the course. The Schedule Type links will be available only when the schedule of classes is available for the selected term.

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.
3.000 Credit hours

Levels: Graduate, Professional, Undergraduate
Schedule Types: Lecture

Offered By: College of Science
Department: Computer Science

Course Attributes:
Upper Division

May be offered at any of the following campuses:     
      West Lafayette

Return to Previous New Search XML Extract
Transparent Image
Skip to top of page