Providing the basic theory and methods that are essential for understanding complexity theory, this second edition of Theory of Computational Complexity emphasizes advances in the field of computational complexity, including newly developed algorithms and novel applications to quantum computing.