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

目录显示

计算理论基础回顾

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

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

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

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

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

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

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

判定器将采取如下策略：其选取 \(\phi\) 中的某一个子句 \(C_i\)，并在该子句中随机选取一个变量 \(x_j\)。接下来，判定器将给其中一个证明器发送 \(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)\) 位的信息。