3 credits
Fall 2025 Lecture Upper DivisionData from last updated 10/3/2025
Fall 2025
Fall 2025 Instructors:
Turing machines and the Church-Turing thesis; decidability; halting problem; reducibility; undecidable problems; decidability of logical theories; Kolmogorov complexity; time classes; P, NP, NP-complete; space classes; Savitch's theorem, PSPACE-completeness, NL-completeness; hierarchy theorems; approximation theorems; probabilistic algorithms; applications of complexity to parallel computation and cryptography.
Course CS 483 from Purdue University - West Lafayette.Prerequisites
BoilerCoursesis an unofficial catalog for Purdue courses
made by Purdue students.
made by Purdue students.