Go to Main Content

Purdue Self-Service



Catalog Entries


Spring 2011
Jun 15, 2024
Transparent Image
Information Select the Course Number to get further detail on the course. Select the desired Schedule Type to find available classes for the course. The Schedule Type links will be available only when the schedule of classes is available for the selected term.

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. Typically offered Fall Spring.
3.000 Credit hours

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

Offered By: College of Science
Department: Computer Science

Course Attributes:
CH Technical Electives, Upper Division

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

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