Conditional Remix & Share Permitted
CC BY-NC-SA
This graduate-level course focuses on current research topics in computational complexity theory. Topics include: 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.
- Subject:
- Applied Science
- Computer Science
- Engineering
- Mathematics
- Material Type:
- Full Course
- Provider:
- MIT
- Provider Set:
- MIT OpenCourseWare
- Author:
- Bavarian, Mohammad
- Moshkovitz, Dana
- Date Added:
- 02/01/2016