CSE 696: Computational Complexity
Modes of computation; complexity classes and complexity measures; compression, speedup, relations between standard classes, hierarchy results; nondeterminism and NP-completeness; relative computability, polynomial hierarchy, NP-hardness; parallel and circuit complexity; probabilistic complexity.
Nonuniform classes: Circuit classes and relations to uniform classes; parallel complexity: Alternating Turing machines, uniformity conditions, NC; Probabilistic classes; Toda's Theorem, interactive protocols.
None presently available.
Ph.D.:
This course does not fulfill core area or core course requirements.
M.S.:
This course fulfills one Theory/Algorithms Core Area requirement.
CSE 596
Course Instances
| Semester | Section | Title | Instructor | Credit Hours | Enrolled |
|---|---|---|---|---|---|
| Fall 2012 | LEC | Computational Complexity | Dr. Alan L. Selman | 3 | 7/30 |
| Spring 2011 | LEC | Computational Complexity | Dr. Alan L. Selman | 3 | 6/30 |
| Spring 2009 | LEC | Computational Complexity | Dr. Alan L. Selman | 3 | 0/ 0 |
