《计算复杂性：现代方法》[55M]百度网盘pdf下载

计算复杂性：现代方法百度网盘pdf下载

作者:

简介:本篇主要提供计算复杂性：现代方法pdf下载

出版社：机械工业出版社

出版时间：2015-11

pdf下载价格：0.00￥

免费下载

前去下载

书籍下载

下载地址

内容介绍

编辑推荐

　　计算复杂性理论的研究是计算机科学重要的研究领域之一，而Chistos H. Papadimitriou是该领域知名的专家之一。

　　计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域，是理论计算机科学研究的重要内容。复杂性是计算（复杂性类）和应用（问题）之间复杂而核心的部分。

　　本书是一本全面阐述计算复杂性理论及其近年来进展的教科书，内容颇为深奥，重点介绍复杂性的计算、问题和逻辑。本书主要内容包含算法图灵机、可计算性等有关计算复杂性理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外（如多项式空间等）复杂性类的介绍。每章最后一节包括相关的参考文献、注解、练习和问题，很多问题涉及更深的结论和研究。

内容简介

　　《计算复杂性：现代方法》系统地介绍计算复杂性理论的经典结果和近30年来取得的新成果，旨在帮助读者了解和掌握复杂性理论中的基本结果、思维方法、主要工具、研究前沿和待决问题。本书分为三部分。*部分（第1～11章）较宽泛地介绍了复杂性理论，包括复杂性理论的经典结果和一些现代专题。第二部分（第12～16章）讨论了各种具体计算模型上的计算复杂性下界。第三部分（第17～23章）主要是1980年以后人们在复杂性理论方面获得的进展，内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。本书内容丰富，结构灵活，语言流畅，是从事计算复杂性理论及相关领域的研究人员必不可少的参考书，非常适合作为打算进入该研究领域的研究生、博士生快速接触研究前沿的参考资料，还非常适合作为普通高校计算机科学与技术、数学专业本科生、研究生相关课程的教材，其中的高级专题还可以作为博士生相关讨论班的素材。

作者简介

　　克里斯特斯 H. 帕帕季米特里乌（Christos H. Papadimitriou），是当今计算机科学界最活跃和有影响力的科学家之一。Papadimitriou拥有普林斯顿大学博士学位，现为加州大学伯克利分校计算机科学系教授。他曾在哈佛大学、麻省理工学院、雅典工艺大学、斯坦福大学、加州大学圣地亚哥分校任教。他是美国科学院院士、美国工程院院士和美国人文科学院院士。他于2002年获得高德纳奖，2012年获得哥德尔奖。他的主要研究领域是算法和复杂性，以及它们在优化、数据库、人工智能、经济和互联网等方面的应用，曾撰写此领域教科书5本，发表论文数篇。

精彩书摘

　　《计算复杂性：现代方法》：
　　本章注记和历史
　　量子计算机是可逆的（引理10.7）。在开始着手研究量子计算之前，人们曾对可逆计算这一领域开展了研究（Ben87）。可逆计算旨在从热力学角度找出传统计算机计算速度的局限性。Toffoli门正是在这样的背景下被提出的。
　　1982年，费曼（Fey82）指出，在传统的图灵机上似乎无法高效地模拟量子力学，并建议建立量子计算机来执行这种模拟。（事实上，如果量子计算机真的被建造出来，则它的主要应用也就是模拟传统计算机。）同时，费曼还指出，量子图灵机的计算能力可能会强于传统图灵机。1985年，德吾奇（Deutsch）首先形式地定义了量子图灵机，虽然现在看来他的定义不尽令人满意。后来，更完善的定义出现在德吾奇，约萨（Josza）的论文（DJ92）和伯恩斯坦（Bernstein），瓦兹拉尼（Vazirani）的论文（BV93）中。后一篇论文首次证明了通用量子图灵机的存在性，并证明了用通用量子图灵机模拟其他量子图灵机时仅导致计算效率下降一个多项式因子。姚期智（Ya093）将这些结果推广到了量子线路上，本章给出的量子计算的定义源自姚期智。（与量子线路相比，伯恩斯坦一瓦兹拉尼定义的量子图灵机容忍噪音的能力较差，因此被认为是不太可能被实现的。）德吾奇（Deu89）证明了某个3量子门在量子线路中是通用量子门，而索洛维（Solovay）（1995年未发表的手稿）和基塔耶夫（Ki-taev）各自独立地证明了，通用量子门可以将任意酉阵近似到量子门个数的指数精度，由此得到定理10.12（尽管本章表述该定理时使用了书（NCOO）中提到的特殊通用基）。
　　……

前言/序言

　　Complexity，A Modern Approach计算复杂性理论在过去三十多年中发展迅速。自1990年以来取得的出人意料的结果和基础性的结果本身就可以写出一部书。这些结果涉及的领域非常广泛，包括：经典复杂性类的概率型新定义（IP=PSPACE和各种PCP定理）以及它们在近似算法中的应用，肖尔（Shor）为量子计算机设计的整数因数分解算法，对人们目前处理著名的P?=NP问题　译文用“P?=NP”来表示原文中的“P versus NP”。——译者注的各种方法为什么未能获得成功的理解，去随机化理论和基于计算难度的伪随机性，以及随机性提取器和扩张图等伪随机对象的优美构造。

　　本书的目标就是为了在介绍复杂性理论经典结果的同时阐述近年来取得的新成果。写作本书的出发点是让它既可以作为教科书使用，也可以作为自学的参考书使用。这意味着我们在写作本书时必须兼顾广泛的读者。为实现这一目标，我们对全书进行了精心的设计。我们实际上还假设读者不具备关于计算的任何背景而且只具备附录A中概述的*少数学背景。我们为本书提供了一个网站http://www.cs.princeton.edu/theory/complexity。网站上列出了相关的辅助材料，包括用本书作为教材时的详细教学计划、全书各个章节的草稿，以及涵盖相关主题的其他资源的超链接。全书始终强调各个概念在何种场合下是有用的，以及为什么这些概念要这样定义。在一些关键的定义上，我们还用一些例子进行了阐释。为了使行文流畅，我们力争尽可能少地引用参考文献。参考文献的引用有两种情况，其一是当前的结果用到了文献中的标准术语，其二是我们觉得为特定的结果提供一些历史信息将有助于阐明其动机和适用的场合。每章末尾有一个单独的注记小节，它简明扼要地讨论了更多的相关工作。当一个概念有多种定义时，我们会选择相对简单的定义；当一个结果有多种证明时，我们会选择能证得更具一般性的结论或者*优结论的证明。

　　全书分为三个部分。

　　第一部分：基本复杂性类。这个部分是对复杂性理论的广泛介绍。从图灵机的定义和可计算理论的基本概念开始，这个部分涵盖了各种基本的时间复杂性类和空间复杂性类，还包含了更现代的一些专题，包括概率算法、交互式证明、密码学、量子计算机和PCP定理及其应用。

　　第二部分：具体计算模型的下界。这个部分讨论在线路和判定树等具体计算模型上用算法求解各种计算任务所需的计算资源的下界。这些计算模型初看起来与图灵机有很大的区别，但更深入研究将得到它们与图灵机之间的有趣的相互联系。

　　第三部分：高级专题。这个部分主要是1980年以后人们在复杂性理论方面获得的进展。内容包括计数复杂性、平均复杂性、难度放大、去随机化和伪随机性、PCP定理的证明以及自然证明。

　　本书的每一章几乎都可以单独进行阅读，但是第1章、第2章和第7章不能跳过。正是这种设计，使得本书可以适用于下面各种不同的读者。

　　物理学家、数学家和其他科学家。这个读者群对计算复杂性理论越来越感兴趣，他们特别感兴趣的是那些高调的研究结果，例如肖尔算法(Shor algorithm)和*近取得的确定型素性测试算法。这个读者群的知识储备丰富，他们可以快速通读第一部分，然后迅速进入第二部分和第三部分，也可以单独阅读各个章节并找到理解当前研究结果所需的每个知识点。

　　本身不从事计算复杂性理论研究的计算机科学家。他们既可以用本书来自学，也可以将本书作为参考书，还可以用本书来讲授本科生或研究生的计算理论或计算复杂性理论课程。

　　从事计算复杂性理论研究或者打算从事这种研究的任何人，包括教授和学生。本书讲解*新研究结果和高级专题的详细程度可以让打算从事复杂性理论和相关领域研究的读者具有充足的知识储备。

　　本书可以作为如下几类课程的教科书。

　　本科生的计算理论课程。很多计算机科学系都用西普赛尔(Sipser)的书［Sip96］来为本科生开设计算复杂性理论这门课。本书可以用作对西普赛尔的教材在一些更现代的专题上的补充，这些专题包括概率算法、密码学和量子计算。相比于自动机理论和可计算理论的精细划分，本科生可能会发现这些专题更能令人耳目一新。所需的数学背景是能够比较自然地阅读数学证明以及离散数学知识，这些知识通常涵盖于“离散数学”或“计算机数学”等课程中，而目前多数计算机系都已经开设了这样的课程。

　　为高年级本科生和新入学的研究生开设的计算复杂性导论课程。本书还可以用来为计算机科学专业的高年级本科生和新入学的研究生开设计算复杂性导论课程，以替代1994年帕帕迪米特里奥(Papadimitriou)撰写的教材［Pap94］（该书未包含很多*近的研究成果）。这门课程可以讲授第一部分的多数专题，再零星地讲授第二部分和第三部分的内容，并且假设学生具备了一定的算法知识和计算理论的知识。

　　研究生的计算复杂性课程。本书也可以作为研究生的计算复杂性课程的教材，以培养学生在复杂性理论或者算法和机器学习等相关领域开展研究的能力。这门课程可以用第一部分来复习基本知识，然后进入第二部分和第三部分的高级专题中。本书的内容多于一个学期的教学内容，网站上提供了这门课程的其他几种教学大纲。

　　研究生讨论班或高级课程。第二部分和第三部分中的各个独立章节都可以用于复杂性理论的讨论班和高级课程，比如关于去随机化、PCP定理和下界的讨论班或高级课程。

　　本书网站为这些课程提供了几种教学计划和素材。如果你在课程中采用了本书，我们乐意了解情况并得到你的反馈。我们要求你不要在网上发布本书习题的答案，这样其他人才可以用这些习题给学生留作业或出考题。

　　在写作本书的过程中，我们清醒地意识到我们不得不舍弃对一些重要结果的讲述。我们希望本书对其他教材的大量引用有助于读者的进一步阅读。同时，我们还计划对本书的网站进行周期性的更新，以帮助读者了解和浏览他们感兴趣的新结果。

　　*重要的是，我们希望通过本书将计算复杂性中激动人心的研究结果以及它们对其他学科的深刻影响传递给读者。

　　让我们一起为彻底解决P?=NP问题而努力吧！

　　致　谢Computational Complexity，A Modern Approach我们对复杂性理论的理解是在与同行交流的过程中逐步形成的。我们从他们身上学到了太多的东西，要感谢的人也远不止下面提到的这些人。Boaz首先要感谢两位导师Oded Goldreich和Avi Wigderson，是他们把他引入了理论计算机科学的世界并不断影响他在这一领域的思想。

　　我们感谢Luca Trevisan，他（从8年前开始！）对本书的写作提供了持续不断的鼓励，并为第一版草稿中若干章节的撰写提供了大量帮助。一些同行毅然地同意并审阅了本书部分章节的早期草稿，他们是：Scott AaronsonNoga AlonPaul BeameIrit DinurVenkatesan GuruswamiJonathan KatzValentine KavanetsSubhash KhotJirˇí MatouekKlaus MeerOr MeirMoni NaorAlexandre PintoAlexander RazborovOded RegevOmer ReingoldRosen ShaltielMadhu SudanAmnon TaShmaIannis TourlakisChris UmansSalil VadhanDieter van MelkebeekUmesh Vazirani和Joachim von zur Gathen.特别感谢Jirˇí、Or、Alexandre、Dieter和Iannis，他们对本书的很多章节给出了具体而有用的评述。

　　很多人指出了本书的拼写错误和缺陷，他们给出的评述帮助我们改进了文字质量，还有一些人回答了我们在特定证明中提出的问题或者给出了相应的参考文献。在此，一并对他们表示感谢，他们是：Emre AkbasEric AllenderDjangir BabayevMiroslav BalazArnold BeckmannIdo BenEliezerSiddharth BhaskarGoutam BiswasShreeshankar BodasJosh BronsonArkadev ChattopadhyayBernard ChazelleMaurice CochandNathan CollinsTim CrabtreeMorten DahlRonald de WolfScott DiehlDave DodyAlex FabrikantMichael FairbankJoan FeigenbaumLance FortnowMatthew FranklinRong GeAli GhodsiParikshit GopanlanVipul GoyalStephen HarrisJohan HstadAndre HernichYaron HirschThomas HolensteinXiu HuichaoMoukarram KabbashBart KastermansJoe KilianTomer KotekMichal KoucySebastian KuhnertKatrina LaCurtsChangWook LeeJames LeeJohn LenzMeena MahajanMohammad MahmoodyGhidaryShohei MatsuuraMauro MazzieriJohn McCulloughEric MilesShira MitchellMohsen MomeniKamesh MunagalaRolf NeidermeierRobert NowotniakTaktin OeyToni PitassiEmily PitlerAaron Potechin Manoj PrabhakaranYuri PritykinAnup RaoSaikiran RapakaNicola RebagliatiJohan RichterRon RivestSushant SachdevaMohammad Sadeq DoustiRahul SanthanamCem SayRobert SchweikerThomas SchwentickJoel SeiferasJonah ShermanAmir ShpilkaYael SnirNikhil SrivastavaThomas StarbirdJukka SuomelaElad TsurLeslie ValiantVijay VaziraniSuresh VenkatasubramanisnJustin VincentFoglesongJirka VomlelDaniel WichsAvi WigdersonMaier WillardRoger WolffJureg WullschlegerRui XueJon YardHenry YuenWu Zhanbin和Yi Zhang.谢谢你们！

　　毫无疑问，上述列表仍有可能遗漏了这些年向我们的创作提供过帮助的人，我们对那些被遗漏的人表示感谢和歉意。

　　本书用LATEX进行排版为此特别感谢Donald Knuth和Leslie Lamport。Stephen Boyd和Lieven Vanderberghe爽快地向我们提供了他们写作《凸优化》一书时使用的LATEX宏定义。

　　*重要的是，感谢我们的家人——Silvia、Nia、Rohan Arora和Ravit、Alma Barak。

　　Sanjeev要感谢父亲，父亲是他创作本书的源泉。

查看全部↓