Description based on print version record.

Includes bibliographical references (p. 549-573) and indexes.

Notational conventions -- The computational model, and why it doesn't matter -- NP and NP completeness -- Diagonalization -- Space complexity -- The polynomial hierarchy and alternations -- Boolean circuits -- Randomized computation -- Interactive proofs -- Cryptography -- Quantum computation -- PCP theorem and hardness of approximation : an introduction -- Decision trees -- Communication complexity -- Circuit lower bounds : complexity theory's Waterloo -- Proof complexity -- Algebraic computation models -- Complexity of counting -- Average case complexity : Levin's theory -- Hardness amplification and error-correcting codes -- Derandomization -- Pseudorandom constructions : expanders and extractors -- Proofs of PCP theorems and the Fourier transform technique -- Why are circuit lower bounds so difficult?