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 fulfills one Theory/Algorithms Core Area (Depth) requirement.

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