| Course Code: CS505 Course Name: Structural Complexity Prerequisites: CS301, CS302 Syllabus: Models of computation: automata, Turing machines, oracle Turing machines. Time and space bounded computations. Central complexity classes: invertibility, honesty, NP-Complete Sets, PSPACE-complete sets, padding arguments, space bounded reducibility. Time bounded reducibility: relativized classes, tally and sparse sets, self-reducibility. Nonuniform complexity: Boolean circuit complexity, polynomial advice. logarithmic advice. Self-producible circuits. probabilistic complexity classes. Uniform diagonalization. The polynomial time hierarchy. Alternation, Kolmogorov complexity. References: 1. J. L. Balcazar, J. Diaz and J. Gabarro, Structural Complexity, Vols 1 & 2, EATCS Monographs, Springer-Verlag, 1987. 2. J. Van Leeuwen, Handbook of Theoretical Computer Science, Vol A, Elsevier and MIT Press, 1990. |