The course presents the main results of computational complexity theory, including complexity classes, reducibilities, and complete sets. Relationships between time and space complexity, between serial and parallel computation, and among deterministic, probabilistic, and nondeterministic computation. Complexity theoretic notions of randomness.
Copyright © 2019, Rutgers, The State University of New Jersey. All rights reserved.