Go to Main Content

Purdue Self-Service



Detailed Course Information


Spring 2023
Mar 31, 2023
Transparent Image
Information Select the desired Level or Schedule Type to find available classes for the course.

CS 48300 - Introduction To The Theory Of Computation
Credit Hours: 3.00. 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.
3.000 Credit hours

Levels: Undergraduate, Graduate, Professional
Schedule Types: Distance Learning, Lecture

Offered By: College of Science
Department: Computer Science

Course Attributes:
Upper Division

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

Undergraduate level CS 38100 Minimum Grade of C

Short Title: Theory Of Computation

Course Configurations:

Configuration 1: 3.0 Credits
Schedule Type Weekly Contact Hours Instructional Credit Distribution
Lecture 3 3.0

Transparent Image
Skip to top of page
Release: 8.7.2