Course Websites
ECE 579 - Computational Complexity
Last offered Fall 2024
Official Description
Course Information: Same as CS 579. See CS 579.
Related Faculty
Subject Area
- Computer Engineering
Course Director
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, PSPACE; complete problems; randomness and complexity classes RP, RL, BPP; alternation, polynomial-time hierarchy; circuit complexity, parallel complexity, NC, RNC; relativized computational complexity; time-space trade-offs.
Notes
Same as CS 579 and MATH 579.
Topics
- Turing machines, nondeterminism, hierarchy and simulation theorems
- Deterministic and nondeterministic sequential classes
- Random sequential classes
- Alternation, polynomial-time hierarchy
- Circuit complexity, parallel complexity
- Relativized computational complexity
- Time-space trade-offs
- Review
Detailed Description and Outline
Topics:
- Turing machines, nondeterminism, hierarchy and simulation theorems
- Deterministic and nondeterministic sequential classes
- Random sequential classes
- Alternation, polynomial-time hierarchy
- Circuit complexity, parallel complexity
- Relativized computational complexity
- Time-space trade-offs
- Review
Same as CS 579 and MATH 579.
Texts
D.-Z. Du and K.-I. Ko, Theory of Computational Complexity, Wiley, 2000.
Current literature.
Current literature.
| Title | Section | CRN | Type | Hours | Times | Days | Location | Instructor |
|---|---|---|---|---|---|---|---|---|
| Computational Complexity | F | 51781 | LCD | 4 | 1530 - 1645 | T R | 1302 Siebel Center for Comp Sci | Michael A. Forbes |