Purdue University - Department of Computer Science - CS 483: Theory of Computation
Skip to main content

CS 483: Theory of Computation

Topics include:

  1. Turing machines and the Church-Turing thesis

  2. Decidability, the halting problem

  3. Reducibility, undecidable problems

  4. Decidability of logical theories, Kolmogorov complexity

  5. Time classes: P, NP, and NP-complete

  6. Space classes: Savitch's theorem, PSPACE-completeness, and NL-completeness

  7. Hierarchy theorems, approximation algorithms, probabilistic algorithms

  8. Parallel computation, cryptography

2004.08

Last Updated: Apr 25, 2017 4:48 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone:(765) 494-6010 • Fax: (765) 494-0739

Copyright © 2016 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.