Go to Main Content

Purdue Self-Service

 

HELP | EXIT

Detailed Course Information

 

Spring 2024
Mar 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: Graduate, Professional, Undergraduate
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


Prerequisites:
Undergraduate level CS 38100 Minimum Grade of C

Return to Previous New Search
Transparent Image
Skip to top of page
Release: 8.7.2.4