阿罗拉编著的《计算复杂性的现代方法》是一部将所有有关复杂度知识理论集于一体的教程。将最新进展和经典结果结合起来，是一部很难得的研究生入门级教程。既是相关科研人员的一部很好的参考书，也是自学人员很难得的一本很好自学教程。本书一开始引入该领域的最基本知识，然后逐步深入，介绍更多深层次的结果，每章末都附有练习。对复杂度感兴趣的人士，物理学家，数学家以及科研人员这本书都是相当受益。

About this bOok

Acknowledgments

Introduction

 0 Notational conventions

PARTONE: BASIC COMPLEXITY CLASSES

 1 The computational model--and why it doesn't matter

 2 NP and NP completeness

 3 Diagonalization

 4 Space complexity

 5 The polynomial hierarchy and alternations

 6 Boolean circuits

 7 Randomized computation

 8 Interactive proofs

 9 Cryptography

 10 Quantum computation

 11 PCP theorem and hardness of approximation: An introduction

PART TWO: LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS

 12 Decision trees

 13 Communication complexity

 14 Circuit lower bounds: Complexity theory's Waterloo

 15 Proof complexity

 16 Algebraic computation models

PART THREE: ADVANCED TOPICS

 17 Complexity of counting 

 18 Average case complexity: Levin's theory

 19 Hardness amplification and error-correcting codes

 20 Derandomization

 21 Pseudorandom constructions: Expanders and extractors

 22 Proofs of PCP theorems and the Fourier transform technique

 23 Why are circuit lower bounds so difficult?

Appendix: Mathematical background

Hints and selected exercises

Main theorems and definitions

Bibliography

Index

Complexity class index