计算 机 科 学 书 HZ BOOKS 华章教育 CAMBRIDGE 计算复杂性 现代方法 桑杰夫·阿罗拉（SanjeevArora [美] 博阿兹·巴拉克（BoazBarak） 骆吉洲 译 Computational Complexity A Modern Approach Computational Complexity AModern Approach SanjeevArora and BoazBarak CAMBRIDGE 机械工业出版社 ChinaMachine Press 计算复杂性现代方法 Computational Complexity A Modern Approach 计算复杂性理论是理论计算机科学研究的核心。本书基本上包含了计算复杂性领域近30年来所有令 人兴奋的成果，是对此领域感兴趣的读者的必读书籍 阿维·维德森（AviWigderson），普林斯顿人学数学学院高级研究所教授 本书综述了复杂性理论的所有重大成果，对学生和研究者来说是非常有用的资源 迈克尔·西普塞（MichaelSipser），麻省理工学院数学系教授 本书既描述了计算复杂性理论最近取得的成果，也描述了其经典结果。具体内容包括：图灵机的定 义和基本的时间、空间复杂性类，概率型算法，交互式证明，密码学，量子计算，具体的计算模型的下 界（判定树、通信复杂度、恒定的深度、代数和单调线路、证明复杂度），平均复杂度和难度放大，去 随机化和伪随机数产生器，以及PCP定理。 本书仅要求读者有完备的数学知识，可以作为任何对计算复杂性感兴趣的读者的自学参考书，包括 物理学家、数学家和其他科学家，也可以作为各种课程和研讨会的教科书。 作者简介 桑杰夫·阿罗拉（SanjeevArora）普林斯顿大学计算机科学系教授，在概率可验证 题中心”，该项目由国家科学基金资助。 博阿兹·巴拉克（BoazBarak）现为哈佛大学计算机科学系教授，哈佛大学工学院 计算理论研究组成员，同时还是微软新英格兰研究院首席研究员，之前是普林斯顿大学计 算机科学系副教授。他在计算复杂性和密码学方面，特别是“非黑盒”技术方面，取得了 基础性的研究成果。 -51899-0 CAMBRIDGE UNIVERSITYPRESS www.cambridge.org 投稿热线：（010）88379604 华章网站：www.hzbook.com 客服热线：（010）8837899188361066 51899 网上购书：www.china-pub.com 购书热线：（010）68326294 88379649 68995259 数字阅读：www.hzmedia.com.cn 定价：129.00元 计算复杂性 现代方法 柔杰夫·阿罗拉（SanjeevArora） [美] 著 博阿兹·巴拉克（BoazBarak） 骆吉洲译 Computational Complexity AModernApproach Computational complexity Modern Approach Sanjeev Arora and Boaz Barak CAMBRIDGI 机械工业出版社 ChingMachinePress 图书在版编目（CIP）数据 计算复杂性：现代方法／（美）阿罗拉（Arora，S.），（美）巴拉克（Barak，B.）著；骆吉洲译 一北京：机械工业出版社，2015.11 （计算机科学丛书） 书名原文：ComputationalComplexity：AModernApproach ISBN978-7-111-51899-0 I.计I.①阿②巴③骆.III.计算复杂性IV.TP301.5 中国版本图书馆CIP数据核字（2015）第253023号 本书版权登记号：图字：01-2012-3791 SanjeevArora andBoazBarak:Computational Complexity,AModernApproach(ISBN 978-0-521-42426-4) Sanjeev Arora and Boaz Barak 2009. This simplified Chinesefor thePeople's Republic of China(excludingHongKong, MacauandTaiwan)ispublishedbyarrangementwiththePressSyndicate of theUniversity ofCambridge,Cambridge,UnitedKingdom. CambridgeUniversityPressandChina MachinePress in2016. This simplified Chinese is authorized for sale in the People's Republic of China (excludingHongKong,MacauandTaiwan)only.Unauthorized exportof this simplified Chinese isaviolation of the Copyright Act.No part of-this publication maybereproduced ordistributedbyanymeans,orstoredinadatabaseorretrievalsystem,withouttheprior writtenpermissionof CambridgeUniversityPressandChina MachinePress. 本书原版由剑桥大学出版社出版。 本书简体字中文版由剑桥大学出版社与机械工业出版社合作出版。未经出版者预先书面许可，不得 以任何方式复制或抄袭本书的任何部分。 此版本仅限在中华人民共和国境内（不包括香港、澳门特别行政区及台湾地区）销售。 本书系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果，旨在帮助读者了解和掌握 复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。本书分三部分。第一部分（第 1～11章）较宽泛地介绍了复杂性理论，包括复杂性理论的经典结果和一些现代专题。第二部分（第 12～16章）讨论了各种具体计算模型上的计算复杂性下界。第三部分（第17～23章）主要是1980 年以后人们在复杂性理论方面获得的进展，内容包括计数复杂性、平均复杂性、难度放大、去随机化和 伪随机性、PCP定理的证明以及自然证明。 本书内容丰富，结构灵活，语言流畅，是从事计算复杂性理论及相关领域的研究人员必不可少的参 考书，非常适合作为打算进人该研究领域的研究生、博士生快速接触研究前沿的参考资料，还非常适合 作为普通高校计算机科学与技术、数学专业本科生、研究生相关课程的教材，其中的高级专题还可以作 为博士生相关讨论班的素材。 出版发行：机械工业出版社（北京市西城区百万庄大街22号邮政编码：100037） 责任编辑：和静 责任校对：殷虹 印 刷：北京市荣盛彩色印刷有限公司 版 次：2016年1月第1版第1次印刷 开 本：185mm×260mm1/16 印 张：31.25 书 号：ISBN978-7-111-51899-0 定 价：129.00元 凡购本书，如有缺页、倒页、脱页，由本社发行部调换 客服热线：（010）88378991 88361066 投稿热线：（010）88379604 购书热线：（010）68326294 88379649 68995259 读者信箱：[email protected] 版权所有·侵权必究 封底无防伪标均为盗版 本书法律顾问：北京大成律师事务所韩光/邹晓东 「出版者的话 Computational Complexity,AModern Approach 文艺复兴以来，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学 的各个领域取得了垒断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年 间名家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合， 作，不仅擎划了研究的范畴，还揭示了学术的源变，既遵循学术规范，又自有学者个性， 其价值并不会因年月的流逝而减退。 近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求 日益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育 战略上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算 机科学发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国 轨、建设真正的世界一流大学的必由之路。 机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998年开始，我们就 将工作重点放在了避选、移译国外优秀教材上。经过多年的不懈努力，我们与Pearson， McGraw-Hill，Elsevier，MIT，JohnWiley&Sons，Cengage等世界著名出版公司建立 了良好的合作关系，从他们现有的数百种教材中甄选出AndrewS.Tanenbaum，Bjarne Stroustrup,BrainW.Kernighan,Dennis Ritchie,JimGray, AfredV.Aho,John E.Hopcroft，JeffreyD.Ullman,AbrahamSilberschatz，William Stallings，Donald E.Knuth，JohnL.Hennessy，LarryL.Peterson等大师名家的一批经典作品，以“计算 机科学丛书”为总