Legacy Course Catalog
C S 584 - Theory Of Computation And Computational Complexity
| Effectivity: | 08/20/2001 - 05/10/2003 @ Purdue West Lafayette Traditional |
|---|---|
| Credits: | 3 |
| Instructional Types: | Lec |
| Usually Offered: | spr |
| Short Title: | Thry Comp/Comp Complex |
| Description: | The theory of general purpose programming systems. Recursive and partial-recursive functions; recursive and recursively enumerable sets. The Church-Turing thesis. The recursion theorem, Roger's translation theorem, Rice's undecidability theorem. The general theory of computational complexity: there are no general solutions to natural optimization problems. Complexity for specific models of computation: the polynomial complexity classes P, NP, and PSPACE; NP-hard and PSPACE-hard problems, inherently exponential problems. |
| 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.
