3 credits
Spring 2026 Lecture Upper DivisionData from last updated 12/30/2025
Spring 2026
Spring 2026 Instructors:
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.
Course CS 584 from Purdue University - West Lafayette.Prerequisites
One of
Student attribute GR
Restrictions
BoilerCoursesis an unofficial catalog for Purdue courses
made by Purdue students.
made by Purdue students.