Legacy Course Catalog
C S 483 - Introduction To The Theory Of Computation
| Effectivity: | 01/10/2005 - Fall 2007 *** @ Purdue West Lafayette Traditional |
|---|---|
| Credits: | 3 |
| Instructional Types: | Lec |
| Usually Offered: | fal spr |
| Short Title: | Theory of Computation |
| Description: | 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. |
| School: | School Of Science |
| Department: | Computer Science |
| Credit By Exam: | NO |
| Repeatable Flag: | NO |
| Temporary Flag: | NO |
| Full Time Privilege Flag: | NO |
| Honors Flag: | NO |
| Registration Approval Type: | Department |
| Variable Title Flag: | NO |
Fall 2007 *** indicates the course was still an active course and was transferred to the Banner Catalog effective Spring 2008. This course was not expired Fall 2007.
