UB - University at Buffalo, The State University of New York Computer Science and Engineering

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.:

None.

M.S.:

This course does not fulfill core area (depth) or core course (breadth) requirements.

CSE 596

Course Instances
Semester Section Title Instructor Credit Hours Enrolled
Spring 2015 LEC Computational Complexity Dr. Kenneth W. Regan 3 5/20
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
Spring 2005 LEC Theory Of Computation 2 Dr. Alan L. Selman 3 6/40
Fall 2001 LEC Theory Of Computation 2 Dr. Alan L. Selman 3 4/22
Spring 1999 LEC Theory Of Computation 2 Dr. Kenneth W. Regan 3 6/24
Valid XHTML 1.0 Transitional