Remix and Share
Advanced Complexity Theory, Fall 2001
(Complete Item Description)
- Abstract:
Current research topics in computational complexity theory. Nondeterministic, alternating, probabilistic, and parallel computation models. Boolean circuits. Complexity classes and complete sets. The polynomial-time hierarchy. Interactive proof systems. Relativization. Definitions of randomness. Pseudo-randomness and derandomizations. Interactive proof systems and probabilistically checkable proofs. The topics for this course cover various aspects of complexity theory, such as the basic time and space classes, the polynomial-time hierarchy and the randomized classes. This is a pure theory class, so no applications were involved.
- Subject:
- Mathematics and Statistics, Science and Technology
- Grade Level:
- Post-secondary
- Collection:
- MIT OpenCourseWare
