Computational Complexity

1.5 credits · Graduate

Elements of the theory of computational complexity. Topics covered include: the distinction between tractable and intractable problems; definition of computational models and complexity classes; techniques for comparing the complexity of problems; the classes P and NP; completeness; auxiliary pushdown automata; alternating Turing machines; the polynomial time hierarchy; the classes Polynomial Space and Logarithm Space; probabilistic complexity classes; models of parallel computation; randomized computation.