跳到正文

CSCI3360

计算复杂度导论

计算模型、非确定性与归约、空间复杂度、随机计算、电路与计数、多项式层级、交互证明及概率可检验证明。

10 章 · 33 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 33 节已标记完成

下一节: 随机计算与放大

完成记录保存在此浏览器中。

这门课在网上

CSCI3360 笔记里的内容

定理卡
94
定义
50
反例
33
概念视角
17
思想史
1
证明透视
33

有思想史的节

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 33 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 94 · 定义 50 · 反例 33 · 概念视角 17 · 思想史 1 · 证明透视 33

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 33 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 4 节

随机化复杂度

公平随机位、RP、BPP、放大、零错误计算与恒等测试

定理 10 · 定义 4反例 4视角 1证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    随机计算与放大

    定义单边错误与双边错误,并利用独立重复证明多数表决放大。

  2. 1.2

    零错误随机计算

    以有界截断及独立单边算法证明零错误类别的刻画。

  3. 1.3

    方差界与随机恒等检验

    证明方差放大界,并分析使用公平比特的多项式恒等测试。

  4. 1.4

    仿射哈希与有限独立性

    证明素数域上的两两独立性,并区分哈希值独立与碰撞事件独立。

第 2 章 · 4 节

非确定性与归约

NP 与 coNP 证书、多项式归约,以及 3-SAT 到 CLIQUE 的证明。

定理 10 · 定义 11反例 5视角 3证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    非确定性、归约与完全性

    区分 NP 与 coNP 证书并证明图归约,以 3-SAT 困难性为背景。

  2. 2.2

    把验证者转化为可满足性实例

    为有界计算构造布尔电路,并证明电路可满足性是 NP 完全的。

  3. 2.3

    门约束、SAT 与三文字子句

    用辅助变量保持电路的共享结构,并通过证明两个方向与规模界来证明可满足性归约。

  4. 2.4

    见证搜索、判定与类 DP

    从判定查询中恢复多项式长度的见证,并谨慎地结合 NP 与 coNP 条件。

第 3 章 · 7 节

空间与可达性

空间模型、有向可达性与格局计数。

定理 21 · 定义 14反例 7视角 4证明透视 7

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    空间与有向可达性

    定义对数空间计算,证明有向可达性属于 NL 及 NL 包含于 P。

  2. 3.2

    Savitch 定理:模拟非确定性空间

    通过隐式格局图证明一般的平方空间模拟,解释多项式空间类相等及归约的复合。

  3. 3.3

    量化布尔公式、空间与交互式证明

    证明 TQBF 是 PSPACE 完全的,并证明交互式证明具有多项式空间上界。

  4. 3.4

    可达性的完全性与中点递归

    构造格局图归约并分析确定性的中点递归。

  5. 3.5

    为什么非确定性对数空间在补运算下封闭

    利用归纳计数在对数空间内验证不可达性。

  6. 3.6

    2-SAT、蕴含图与 NL 完全性

    证明蕴含图判据,并用对数空间可达性刻画二文字可满足性。

  7. 3.7

    确定性空间层级定理

    利用格局数界与有界模拟,证明更多的空间能够判定严格更多的语言。

第 4 章 · 4 节

计算与模型

判定问题、资源界限、编码与不可判定性。

定理 10 · 定义 5反例 4视角 1思想史 1证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    计算、资源与对角化

    定义计算资源,并用计数与对角化研究可判定性。

  2. 4.2

    用一条纸带模拟多条纸带

    区分旧、新读写头标记,证明固定纸带数的多项式时间稳健性。

  3. 4.3

    确定性时间层级定理

    利用带时钟的通用模拟与对角化方法,分离确定性时间界。

  4. 4.4

    预言机世界与相对化的局限

    构造使 P 与 NP 问题得出相反结果的预言机设定,并追踪对角化构造必须保护哪些查询。

第 5 章 · 3 节

计数与电路

见证计数与多项式规模非一致电路。

定理 9 · 定义 1反例 3视角 1证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    见证计数与非一致电路

    研究 #P 见证计数及非一致电路族。

  2. 5.2

    多数接受与计数

    通过精确多数定义 PP,将其与见证计数联系起来,并证明基本的包含关系与补运算封闭性。

  3. 5.3

    简约归约与积和式

    通过布尔门保持见证计数,解释积和式,并计算其奇偶性。

第 6 章 · 1 节

概率界

Bernoulli 指数尾界的推导。

定理 3 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    Bernoulli 试验的指数尾界

    推导 Bernoulli 指示变量集中界及多数表决放大。

第 7 章 · 1 节

随机计算与建议字符串

重温随机算法的错误放大,并用并集界证明固定随机带的非一致性结论。

定理 3 · 定义 2反例 2视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    错误放大与固定随机性

    重温随机算法的错误放大,并用并集界证明固定随机带的非一致性结论。

第 8 章 · 4 节

交替与多项式层级

交替与多项式层级

定理 11 · 定义 4反例 4视角 3证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    交替与多项式层级

    构建带量词的验证者类,并观察补与嵌套如何改变量词。

  2. 8.2

    层级各层上的完全量化公式

    把多项式时间谓词编码为公式,而不增加一次量词交替。

  3. 8.3

    小电路与多项式层级

    利用非一致见证搜索与显式量词证明 Karp–Lipton 坍缩。

  4. 8.4

    电路建议与层级坍缩

    联系非一致建议与电路,计数小电路,并证明一个有条件的层级坍缩。

第 9 章 · 4 节

交互证明

交互证明

定理 13 · 定义 6反例 2视角 2证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    交互式证明与图非同构

    定义交互式证明中的完备性与可靠性,并分析图非同构协议。

  2. 9.2

    和检验协议(sum-check protocol)

    利用交互式的低次数检验与自适应可靠性证明,验证有限域上所声称的求和值。

  3. 9.3

    从多项式空间到交互式证明

    利用多线性矩阵延拓与 sum-check 证明 PSPACE 包含于 IP。

  4. 9.4

    梅林、亚瑟与公开随机性

    用显式量词定义 MA 与 AM,并证明 MA 包含于 AM。

第 10 章 · 1 节

概率可检验证明

概率可检验证明

定理 4 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    概率可检验证明与间隙归约

    定义随机访问的证明验证,并由一个所陈述的间隙定理推出一个有条件的近似障碍。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情