Complexity Theory

Code: MA519 | L-T-P-C: 3-0-0-6

Prerequistes: MA352 or equivalent

Time and Space complexity, various complexity classes, oracle Turing machine, hierarchy theorems, relations among complexity measures, Savitch's theorem, Borodin's Gap theorem, Blum's speed-up theorem, the union theorem, axiomatic complexity theory, intractable problems, PSPACE-completeness, EXPSPACE-completeness, QBF problem, provably intractable problems, P = NP?, alternating time and space.

Texts:

1. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.
2. M. Sipser, Introduction to the Theory of Computation, Thomson Asia Pte Ltd., 1997.

References:

1. D. Bovet and P. Crescenzi, Introduction to the Theory of Complexity, Prentice Hall, 1993.
2. D. Kozen, Theory of Computation, Springer, 2006
3. D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
4. C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
5. J. L. Balcazar, J. Diaz, J. Gabarro, Structural Complexity, 2nd Ed, Vol 1, Springer-Verlag, 1995.