CSE 696: Computational Complexity
This page refers to the Spring 2009 offering of CSE 696 only. The information on this page does not necessarily apply to every offering of CSE 696.
Spring 2009
21061
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.
CSE 596
Ph.D.: This course does not fulfill core area or core course requirements.
M.S.: This course fulfills one Theory/Algorithms Core Area requirement.
