Publisher's Synopsis
This text looks at: complexity classes; algebraic complexity; interactive proof systems; circuits and other concrete computational models; Kolmogorov complexity; reducibility; complexity and logic; nonapproximability; cryptographic complexity; complexity and learning; quantum computation.