CS 48300 - Introduction to the Theory of Computation
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.
| Usually Offered: | Fall Spring in 2007-08 |
| Credit: | 3 hours (class) |
| Prerequisite: | CS 381 and CS 352, or consent of instructor |
| University Catalog: | CS 483 |
