Go to Main Content

Purdue Self-Service



Detailed Course Information


Summer 2024
Jul 19, 2024
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

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