计算复杂性 现代方法

       阿兰•图灵（Alan Turing）等人对计算的精确定义导致了现代电子计算机的诞生。

       如今，计算机早已融人社会管理、经济活动、工程实践、军事活动、休闲娱乐等现代生活的方方面面，各种计算机软件精彩纷呈、层出不穷。可以说，计算无时无刻地发生在我们的周围。对各种计算问题的计算过程所消耗的时间/空间等资源数量的多少进行量化，进而对各种计算问题进行分类，并研究各类计算问题之间的相互联系，研究近似求解无法精确求解的问题的难度，力争最终解决计算中最核心的问题，围绕这些任务逐渐发展和形成的理论、技术和方法，形成了理论计算机科学中的一门基础性学科—计算复杂性理论。

       它是为各种计算问题合理地选择算法、配置资源并进行软件开发活动的基础。

       计算复杂性理论形成于20世纪五六十年代。1960年，哈特马尼斯（Hartmanis）和斯特恩斯（Stearns）在他们的开创性论文 “On the computational complexity of algo-

rithms”中引入了时间复杂性类并利用对角线方法证明了时间分层定理，由此奠定了计算复杂性理论的基础。在其后的三十年中，人们逐渐得到了各种基本复杂性类、NP完全理论等经典结论，并提出了计算复杂性理论中最核心的问题P子NP。在过去三十多年中，计算复杂性理论发展迅速。自1990年以来，人们取得了大量出人意料的结果和基础性的结果，这些结果涉及的领域非常广泛，包括：经典复杂性类的概率型新定义（IP=

PSPACE 和各种PCP 定理）以及它们在近似算法中的应用，肖尔（Shor）为量子计算机设计的整数因数分解算法，对人们目前处理著名的P子NP 问题的各种方法什么未能获得成功的理解，去随机化理论和基于计算难度的伪随机性，以及随机性提取器和扩张图等伪随机对象的优美构造。

       作为计算机科学与技术相关专业的学生，全面系统地学习计算复杂性中的概念、基本结果、思维方法和重要工具并了解一些悬而未决的问题是十分必要的。本书正是适合于上述目标的一部优秀教科书。

       本书作者桑杰夫•阿罗拉（Sanjeev Arora）和博阿兹•巴拉克（Boaz Barak）都是在普林斯顿大学计算机科学系一直从事复杂性理论研究的著名教授。桑杰夫•阿罗拉在概率可验证明 NP-难问题的可近似性方面取得了基础性的研究成果。博阿兹•巴拉克在计算复杂性理论和密码学方面，特别是“非黑盒”技术方面，也取得了基础性的研究成果。本书已经逐步成为国内外计算复杂性理论课程的标准教材，其翻译和出版对国内读者学习和应用复杂性理论具有重要的意义。有幸承担该书的翻译工作，我们感到十分荣幸。

       本书旨在介绍计算复杂性理论的基本概念、经典结果，近年来取得的有用的结果，帮助读者理解和掌握计算复杂性理论中的思维方法、主要工具和研究前沿。基础概念和经典结果可以帮助读者建立计算复杂性理论的知识框架，掌握复杂性理论的思维方法和证明技巧。高级专题是经典结果的有益补充和延伸，而最新的研究成果和悬而未决的问题则可以帮助读者接触计算复杂性理论研究的最前沿。此外，本书还涉及了一些学术界尚存的争论，这些深人分析和深刻见解也是本书的精髓所在。