算法,计算复杂度与交互式证明系统

两类问题

第一类,可解决的问题;第二类,可验证的问题。

直觉上讲:第二类问题更难,是否存在一个难(无法)验证的问题。

完备性/可靠性

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教材