Publisher's Synopsis
This text on computational complexity covers such topics as: structures of complexity classes; resource-bounded reducibilities; interactive proof systems; computational randomness; circuit complexity; proof complexity; communication complexity; complexity and learning; and Kolmogorov complexity.