两类问题

第一类，可解决的问题；第二类，可验证的问题。

直觉上讲：第二类问题更难，是否存在一个难（无法）验证的问题。

完备性/可靠性

NP

带概率验证的证明系统

Probabilistic Checkable Proof

简要介绍

PCP 定理

“交互式地问问题”

1. 查理的验证算法必须是随机的，否则爱丽丝可以欺骗任何只检测三个比特算法（只要知道固定的检查位）
2. 出错总是有概率的

影响

1. 与随机算法，线性规划，半正定规划
2. 激发了通信复杂度理论的研究
3. 编码理论，随机图理论，傅里叶分析

零知识证明

很有意思的例子

题目：某图的一个三染色

Charlie（学生）：认为不存在图的三染色

Alice（助教）：需要证明图的三染色，但是不能透露 Chalie，因为学生正在考试！

核心：不能学到任何新的知识的证明。

另一个很有意思的例子

题目：区分两只袜子颜色

Charlie：质疑 Alice 知道颜色区别

Alice：让 Charlie 在背后以\(\frac{1}{2}\)概率交换袜子，然后拿出来让 Alice 判断是否交换过。

拜占庭协议的研究方向

过去只考虑\(F\)和\(3F+1\)，其实还有两个参数，轮数\(cicle\)和消息buffer大小\(msg\)。

那引入概率算法就有机会来减少同步的论述\(cicle\)以及消息buffer大小（原本是超多项式的）。

计算理论参考学习

计算理论，复杂度分析

Oded Goldreich教材 （主要和密码学有关系）

Arora Barak教材