Notes on Computational Complexity Theory by James Aspnes
File Type :PDF Number of Pages :180
Description This note provides
an introduction to the theory of computational complexity. Topics covered
includes: Models of computation, Time and space complexity classes,
Nonterminism and NP, Diagonalization, Oracles and relativization, Alternation,
Space complexity, Natural proofs, Randomized classes, Counting classes,
Descriptive complexity and Interactive proofs.
