计算复杂性: 现代方法 - 阿罗拉 巴拉克

本书分为三部分.第一部分介绍了复杂性理论,包括复杂性理论的经典结果和一些现代专题.第二部分讨论了各种具体计算模型上的计算复杂性下界.第三部分主要是1980年以后人们在复杂性理论方面获得的进展,内容包括计数复杂性,平均复杂性,难度放大,去随机化和伪随机性,pcp定理的证明以及自然证明.