Course Description for Computational Complexity

COT6416: Computational Complexity
Prerequisites:COT 3210, COT 4400 or COT 5405 This is a course in structural complexity theory. The focus is on the models of computation and the structure and relationship among the important classes of computational problems such as P, BPP, NP, co-NP, and PSPACE. Results on the hardness of approximating optimization problems which follow from the PCP Theorem and the theory interactive proofs will be presented.