CS505  STRUCTURAL COMPLEXITY  3006 
Prerequisites : CS301, CS302 
Syllabus : Models of computation: automata, Turing machines, oracle Turing machines. Time and space bounded computations. Central complexity classes: invertibility, honesty, NPComplete Sets, PSPACEcomplete sets, padding arguments, space bounded reducibility. Time bounded reducibility: relativized classes, tally and sparse sets, selfreducibility. Nonuniform complexity: Boolean circuit complexity, polynomial advice. logarithmic advice. Selfproducible circuits. probabilistic complexity classes. Uniform diagonalization. The polynomial time hierarchy. Alternation, Kolmogorov complexity. 
Texts :

References : 1. J. L. Balcazar, J. Diaz and J. Gabarro, Structural Complexity, Vols 1 & 2, EATCS Monographs, SpringerVerlag, 1987. 2. J. Van Leeuwen, Handbook of Theoretical Computer Science, Vol A, Elsevier and MIT Press, 1990. 