CS 741: Structural Complexity

Course Contents:

Survey of basic background: models of computations and resource bounded computations. Central complexity classes, notion of complete problems in a class, polynomial time reducibilities and how these relate to each other.

Structure of NP complete sets, p-isomorphism conjecture. Sparse sets in NP. Self reducibility. Relativised classes. Nonuniform complexity. Uniform diagonalization. Polynomial time hierarchy. Interactive proof systems.

Books and References:

J. L. Balcazar, J. Diaz, and J. Gabarro.Structural Complexity I, Springer Verlag, 1988.

R.Book (Editor).Studies in Complexity Theory, Pitman, 1986.

Certain topics form relevant journal and conference papers will be used.