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