CS 640: Computational Complexity

Course Contents:

Complexity Classes. NP and co-NP, Results on structure of NP-complete sets, Sparse NP-hard sets, Basic Inclusions and Separations, Nondeterministic Space Classes, Logarithmic Space, A PSPACE complete problem, Polynomial Hierarchy, PH through Alternating Quantifiers, Universal Relations, Probabilistic Classes, Schwartz-Zippel Lemma and BPP, BPP and its relationship with other Complexity Classes