MIT 18.408 概率可验证证明 学习笔记 一 – 基本概念

计算理论基础回顾

详见 计算理论基础 – OI Wiki

概率性判定器

对于一个语言的概率性判定器,我们需要研究其如下参数:

  1. 完备性(Completeness):其衡量在一个串属于某语言,且输入的证明正确的情况下,判定器接受该串的概率。在该课程中,完备性的参数一般为 1。即,如果一个串属于某语言,且对该串属于对应语言的证明正确的情况下,判定器一定会接受该串。对于 3-SAT 问题来说,一个完备性为 1 的判定器意味着,在输入的赋值使得表达式成真的前提下,判定器会以 1 的概率接受该表达式。
  2. 正确性(Soundness):其衡量在一个串不属于某语言的前提下,判定器接受该串的概率。的例如,一个 3-SAT 的概率性判定器在读入各变量的赋值后,随机抽取整个布尔表达式中的一个子句,如果该子句值为真则接受整个表达式,否则拒绝。设表达式包含 \(m\) 个子句,如果该表达式不可被满足,则容易发现该判定器将以不超过 \(1-\frac{1}{m}\) 的概率接受该表达式。
  3. 局部性(Locality)/查询次数:其衡量判定器读取输入的元素个数。仍然以上文提到的 3-SAT 的概率性判定器为例,其利用了一个包含 3 个变量的子句,因此需要查询 3 个变量的赋值。
  4. 字符集大小:由于任意语言都可以转成 01 串的形式,故不加说明的情况下字符集的大小为 2。

PCP 的组合视角观察 – Gap 问题

以 3-SAT 问题为例,其 Gap 版本包含两个参数 \(c, s\)(\(0 \leq s < c \leq 1\))。输入的布尔表达式一定满足下列两个条件之一:

  • 存在一个赋值,使得表达式中有至少 \(c\) 比例的子句被满足;
  • 不存在一个赋值,使得表达式中有超过 \(s\) 比例的子句被满足。

判定器需要判定输入的布尔表达式属于上述两个类型中的哪一个类型。对于其他判定性问题,可以给出类似的 Gap 问题版本。

这里使用的变量名 \(c, s\),正好对应了判定器所用的 Completeness 和 Soundness 两个参数。

事实上,Gap 问题的困难性在一定程度上与近似优化性问题的困难性是对应的。可以证明,如果 Gap-3-SAT[\(c\), \(s\)] 是 NP-Hard 的,则使得表达式满足的子句数,与最优解之比不低于 \(\frac{s}{c}\) 的近似优化问题也是 NP-Hard 的。

PCP 的通信视角观察

考虑这样一个场景,有一个计算性方面较弱的判定器 \(V\) 和两个强的证明器。证明器的目标是说服验证器 \(V\),让其认为某个 3-CNF 公式 \(\phi\) 是可满足的。不过两个证明器之间被隔离,互相之间不能进行交互。

判定器将采取如下策略:其选取 \(\phi\) 中的某一个子句 \(C_i\),并在该子句中随机选取一个变量 \(x_j\)。接下来,判定器将给其中一个证明器发送 \(C_i\) 中的所有变量,给另外一个证明器仅发送 \(x_j\)。判定器从证明器处获得相应变量的取值后,将验证如下两点:

  • 获取到的对 \(C_i\) 中所有变量的赋值确实满足 \(C_i\);
  • 两个证明器对 \(x_j\) 给出的赋值相同。

这一流程被称为 2-prover-1-round game。事实上该流程可以推广到任意语言 \(L \in \mathrm{NP}\),且根据 PCP 定理,可以得出如下结论:

  • 完备性:如果输入 \(z \in L\),则存在证明器策略使得 \(V\) 一定接受 \(z\);
  • 正确性:如果输入 \(z \not \in L\),则任何证明器策略(即使是恶意策略)都只能做到让 \(V\) 以不超过 \(\frac{1}{3}\) 的策略接受 \(z\)。
  • 查询效率:验证器 \(V\) 利用了 \(O(\log n)\) 的随机性,且其从每个证明器处仅读取 \(O(1)\) 位的信息。

《MIT 18.408 概率可验证证明 学习笔记 一 – 基本概念》上有2条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据