Course Identification

Complexity Theory studies the intrinsic difficulty of computational tasks, and the relationship and connections between different tasks. Computation is studied via the lens of resources such as running time, space, randomness, and interaction. This course is meant to provide an introductions and overview of some of the exciting developments in this field.Specific topics will include:

• revisiting the P-vs-NP Question and NP-Completeness;
• separation results for time and space complexity;
• non-uniform complexity (e.g., P/poly);
• the Polynomial-time Hierarchy;
• the class #P and approximate-#P;
• randomized computations (RP and BPP);
• derandomization;
• probabilistic proof systesms (IP, PCP etc);

Upon successful completion of this course students should be able to:

1. Describe key notions and principles of the field of computational complexity theory.
2. Demonstate familiarity with basic paradigms and techniques of the field of computational complexity theory.
3. Apply notions, principles, paradigms and techniques of computational complexity theory to their own research.
4. Discuss the meaning of the various notions and results of computational complexity theory.

Computational Complexity: A Conceptual Perspective,
Oded Goldreich