你的进度
0/ 33 节已标记完成
下一节: 随机计算与放大
完成记录保存在此浏览器中。
这门课在网上
CSCI3360 笔记里的内容
数字只算这门课 33 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 94 · 定义 50 · 反例 33 · 概念视角 17 · 思想史 1 · 证明透视 33
第 1 章 · 4 节
随机化复杂度
公平随机位、RP、BPP、放大、零错误计算与恒等测试
- 1.1
随机计算与放大
定义单边错误与双边错误,并利用独立重复证明多数表决放大。
- 1.2
零错误随机计算
以有界截断及独立单边算法证明零错误类别的刻画。
- 1.3
方差界与随机恒等检验
证明方差放大界,并分析使用公平比特的多项式恒等测试。
- 1.4
仿射哈希与有限独立性
证明素数域上的两两独立性,并区分哈希值独立与碰撞事件独立。
第 2 章 · 4 节
非确定性与归约
NP 与 coNP 证书、多项式归约,以及 3-SAT 到 CLIQUE 的证明。
- 2.1
非确定性、归约与完全性
区分 NP 与 coNP 证书并证明图归约,以 3-SAT 困难性为背景。
- 2.2
把验证者转化为可满足性实例
为有界计算构造布尔电路,并证明电路可满足性是 NP 完全的。
- 2.3
门约束、SAT 与三文字子句
用辅助变量保持电路的共享结构,并通过证明两个方向与规模界来证明可满足性归约。
- 2.4
见证搜索、判定与类 DP
从判定查询中恢复多项式长度的见证,并谨慎地结合 NP 与 coNP 条件。
第 3 章 · 7 节
空间与可达性
空间模型、有向可达性与格局计数。
- 3.1
空间与有向可达性
定义对数空间计算,证明有向可达性属于 NL 及 NL 包含于 P。
- 3.2
Savitch 定理:模拟非确定性空间
通过隐式格局图证明一般的平方空间模拟,解释多项式空间类相等及归约的复合。
- 3.3
量化布尔公式、空间与交互式证明
证明 TQBF 是 PSPACE 完全的,并证明交互式证明具有多项式空间上界。
- 3.4
可达性的完全性与中点递归
构造格局图归约并分析确定性的中点递归。
- 3.5
为什么非确定性对数空间在补运算下封闭
利用归纳计数在对数空间内验证不可达性。
- 3.6
2-SAT、蕴含图与 NL 完全性
证明蕴含图判据,并用对数空间可达性刻画二文字可满足性。
- 3.7
确定性空间层级定理
利用格局数界与有界模拟,证明更多的空间能够判定严格更多的语言。
第 4 章 · 4 节
计算与模型
判定问题、资源界限、编码与不可判定性。
- 4.1
计算、资源与对角化
定义计算资源,并用计数与对角化研究可判定性。
- 4.2
用一条纸带模拟多条纸带
区分旧、新读写头标记,证明固定纸带数的多项式时间稳健性。
- 4.3
确定性时间层级定理
利用带时钟的通用模拟与对角化方法,分离确定性时间界。
- 4.4
预言机世界与相对化的局限
构造使 P 与 NP 问题得出相反结果的预言机设定,并追踪对角化构造必须保护哪些查询。
第 5 章 · 3 节
计数与电路
见证计数与多项式规模非一致电路。
- 5.1
见证计数与非一致电路
研究 #P 见证计数及非一致电路族。
- 5.2
多数接受与计数
通过精确多数定义 PP,将其与见证计数联系起来,并证明基本的包含关系与补运算封闭性。
- 5.3
简约归约与积和式
通过布尔门保持见证计数,解释积和式,并计算其奇偶性。
第 6 章 · 1 节
概率界
Bernoulli 指数尾界的推导。
- 6.1
Bernoulli 试验的指数尾界
推导 Bernoulli 指示变量集中界及多数表决放大。
第 7 章 · 1 节
随机计算与建议字符串
重温随机算法的错误放大,并用并集界证明固定随机带的非一致性结论。
- 7.1
错误放大与固定随机性
重温随机算法的错误放大,并用并集界证明固定随机带的非一致性结论。
第 8 章 · 4 节
交替与多项式层级
交替与多项式层级
- 8.1
交替与多项式层级
构建带量词的验证者类,并观察补与嵌套如何改变量词。
- 8.2
层级各层上的完全量化公式
把多项式时间谓词编码为公式,而不增加一次量词交替。
- 8.3
小电路与多项式层级
利用非一致见证搜索与显式量词证明 Karp–Lipton 坍缩。
- 8.4
电路建议与层级坍缩
联系非一致建议与电路,计数小电路,并证明一个有条件的层级坍缩。
第 9 章 · 4 节
交互证明
交互证明
- 9.1
交互式证明与图非同构
定义交互式证明中的完备性与可靠性,并分析图非同构协议。
- 9.2
和检验协议(sum-check protocol)
利用交互式的低次数检验与自适应可靠性证明,验证有限域上所声称的求和值。
- 9.3
从多项式空间到交互式证明
利用多线性矩阵延拓与 sum-check 证明 PSPACE 包含于 IP。
- 9.4
梅林、亚瑟与公开随机性
用显式量词定义 MA 与 AM,并证明 MA 包含于 AM。
第 10 章 · 1 节
概率可检验证明
概率可检验证明
- 10.1
概率可检验证明与间隙归约
定义随机访问的证明验证,并由一个所陈述的间隙定理推出一个有条件的近似障碍。