CS 579
CS 579 - Computational Complexity
Fall 2023
| Title | Rubric | Section | CRN | Type | Hours | Times | Days | Location | Instructor |
|---|---|---|---|---|---|---|---|---|---|
| Computational Complexity | CS579 | F | 51780 | LCD | 4 | 1530 - 1645 | T R | 1302 Siebel Center for Comp Sci | Michael A Forbes |
| Computational Complexity | ECE579 | F | 51781 | LCD | 4 | 1530 - 1645 | T R | 1302 Siebel Center for Comp Sci | Michael A Forbes |
See full schedule from Course Explorer
Official Description
Turing machines; determinism and non-determinism; time and space hierarchy theorems; speed-up and tape compression; Blum axioms; structure of complexity classes NP, P, NL, L, and PSPACE; complete problems; randomness and complexity classes RP, RL, and BPP; alternation, polynomial-time hierarchy; circuit complexity, parallel complexity, NC, and RNC; relativized computational complexity; time-space trade-offs. Course Information: Same as ECE 579. 4 graduate hours. No professional credit. Prerequisite: One of CS 473, CSE 414, MATH 473, CS 475 or MATH 475.