Go to Main Content

Purdue Self-Service



Detailed Course Information


Fall 2020
Jul 18, 2024
Transparent Image
Information Select the desired Level or Schedule Type to find available classes for the course.

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: Undergraduate, Graduate, Professional
Schedule Types: Distance Learning, Lecture
All Sections for this Course

Offered By: College of Science
Department: Computer Science

Course Attributes:
Upper Division

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

Must be enrolled in one of the following Programs:     
      Computer Science-PHD
      Computer Science-MS

GR-CS 48300 Course

General Requirements:

Student Attribute: GR
May not be taken concurrently.  )
Course or Test: CS 48300
Minimum Grade of D-
May not be taken concurrently. )

Short Title: Thry Comp/Comp Complex

Course Configurations:

Configuration 1: 3.0 Credits
Schedule Type Weekly Contact Hours Instructional Credit Distribution
Lecture 3 3.0
Configuration 2: 3.0 Credits
Schedule Type Weekly Contact Hours Instructional Credit Distribution
Distance Learning 0 3.0

Transparent Image
Skip to top of page
Release: 8.7.2