COMP_SCI 496: Computational Complexity

Quarter Offered

None ;


Permission of the instructor. In terms of background, COMP_SCI 335 is useful but not necessary if you have done some 300 level math courses. Mathematical maturity is an absolute must.


Computational Complexity theory looks at the computational resources (time, memory, communication,  ...) needed to solve computational problems that we care about, and it is especially concerned with the distinction between "tractable" problems, that we can solve with reasonable amount of resources, and "intractable" problems, that are beyond the power of existing, or conceivable, computers. It also looks at the trade-offs and relationships between different "modes" of computation (what if we use randomness, what if we are happy with approximate, rather than exact, solutions, what if we are happy with a program that works only for most possible inputs, rather than being universally correct, and so on). 

We will start with the basics of complexity theory and look at fundamental notions such as NP-completeness, alternations and the polynomial hierarchy, time and space complexity classes, distinctions between uniform and non-uniform computation and relations among these ideas. The second part of the course will broadly look at the power of randomness in computation and the revolution it led to in our understanding of computation.

The course will closely follow these lecture notes:

INSTRUCTOR: Prof. Anindya De