普林斯顿大学,又译 普林斯敦大学,常被直接称为 普林斯顿,是美国一所私立研究型大学,现为八所常青藤学校之一,绰号为老虎。

VIP内容

计算复杂度理论在过去的三十年里发展迅速。自1990年以来所证明的一系列令人惊讶和基本的结果足以写一本书:这些结果包括经典复杂性类(IP = PSPACE和PCP定理)的新概率定义及其对近似算法领域的影响;使用量子计算机分解整数的肖尔算法;理解为什么目前对著名的P对NP的方法不会成功;基于计算硬度的去随机化和伪随机理论还有伪随机对象的漂亮构造,比如提取器和扩展器。这本书旨在描述在经典结果的背景下复杂性理论的这些最近的成就。它的目的是作为一本教科书,作为自学的参考。这意味着它必须同时迎合许多观众,并且是精心设计的。在本书中,我们解释了特定概念在什么情况下是有用的,以及为什么事物以某种方式被定义。,里面有相关的辅助材料。这包括关于自动机和可计算性理论的网页章节,基于本书的课程的详细教学计划,书中所有章节的草稿,以及涉及相关主题的其他在线资源的链接。

第一部分:基本复杂度类。本卷提供了对该领域的广泛介绍。从图灵机的定义和可计算性理论的基本概念开始,这卷涵盖了基本的时间和空间复杂度类,也包括一些更现代的主题,如概率算法,交互式证明和密码学。

第二部分:具体计算模型的下界。本部分描述了在具体模型(如电路、决策树等)上求解算法任务所需资源的下界。乍一看,这些模型似乎与图灵机非常不同,但深入观察,就会发现有趣的相互联系。

第三部分:高级主题。这部分主要介绍1980年代后期以来的发展情况。它包括平均情况复杂度、去随机化和伪随机化、PCP定理和逼近困难、证明复杂度和量子计算。

成为VIP会员查看完整内容
0
32
参考链接
Top
微信扫码咨询专知VIP会员