证书的选取是为了说服验证者,而随机性的选取则是为了让错误的证书难以通过检验。这两种选取的先后次序至关重要。如果证明者在看到随机硬币之前就写下一条消息,那么这条消息必须经得起之后才选定的随机检验。如果证明者先看到硬币,则证明者可以针对该特定检验量身定制应答。我们将仔细定义这两种情形,并证明:在经过足够强的放大之后,第一类协议可以由第二类协议模拟。
下文所有语言均为 的子集。验证者是一个确定性的多项式时间算法,其输入包括一个输入串、一条消息以及一串相互独立的均匀随机比特。消息长度与随机比特长度的多项式界随验证者一并固定。证明者在计算上不受限制,但必须遵守消息长度的界。为便于阅读,我们取完备性 与可靠性 ;当验证者的随机检验相互独立时,这些常数可以通过放大加以改变。
随机检验之前的消息
定义 9.4.1
(MA 类)
若存在多项式 与多项式时间谓词 ,使得对每个长度为 的输入 ,
成立,则称语言 属于 。
较短的消息可以借助填充与长度分隔符进行编码。消息的内容在随机串被采样之前就已固定。“是”与“否”两个条件分别对其各自类型的所有输入进行量化,而不仅仅针对典型输入,也不针对选定的输入分布。
例题 9.4.2
(着色证书)
设输入为一个有限图,其顶点被显式列出。消息为每个顶点指定三种颜色之一。验证者检查每一条边,当且仅当其两个端点颜色不同时接受;它不需要使用随机比特。对于可 3 着色的图,总存在某条消息被始终接受。对于不可 3 着色的图,每条消息都被始终拒绝。这是一个具有完美完备性与完美可靠性的 MA 协议,它来自一个普通的 NP 见证。无效的颜色或格式错误的编码会被拒绝。
命题 9.4.3
(MA 的基本包含关系)
每个属于 的语言以及每个属于 的语言都属于 。
证明
(证明)
对于 NP 语言,以多项式大小的见证作为消息,运行确定性多项式时间验证者,并忽略随机比特。在“是”实例上,一个接受性的见证的接受概率为一;在“否”实例上,每个见证的接受概率均为零。
对于 BPP 语言,忽略消息,利用验证者的硬币运行该 BPP 判定器。其成功保证对每个固定输入至少为 。特别地,每条消息具有相同的接受概率,因此在“否”实例上所有消息都满足可靠性。这就同时给出了两个包含关系,且无需假设 NP 与 BPP 相等,也无需假设其中一个包含另一个。
应答之前的公开硬币
定义 9.4.4
(AM 类)
在两条消息的公开硬币 协议中,亚瑟(Arthur)首先将随机串 发送给梅林(Merlin);随后梅林发送 。等价地,若存在多项式时间谓词 以及多项式的消息界与随机性界,满足
则语言属于 AM。
这里 可以依赖于已公开的 。由于消息空间是有限的,事件 等价于存在一个在该硬币串上成功的、不受限制的应答策略。可靠性表明,即使是最佳的此类策略,其成功概率至多为 。随机性是公开的;私有硬币的交互式协议需要另行定义与分析。
概念视角组合
接受表格的行与列
对固定的输入,写出一张接受比特的表格:每个消息 占一行,每个随机串 占一列。MA 要求存在某一行,其中至少 的项为 (是实例);或要求每一行至多有 的项为 (否实例)。AM 则计算含有至少一个 的列所占的比例,这个比例须至少为 或至多为 。两个类的区别在于:证明者选取的是一整行,还是每一列中的一格。
例题 9.4.5
(为什么选取的次序很重要)
取一个随机比特 与一个消息比特 ,并令 恰在 时接受。若先固定消息,则两种固定消息中的任何一种被接受的概率均为 。若先公开随机比特,则选取 以概率一成功。这个有限谓词说明了从 到 的变化;它本身并不能证明 MA 与 AM 是不同的类。
常见错误
(同样的可靠性界在公开硬币下不一定保持)
假设每条固定消息欺骗随机检验的概率至多为 。由此并不能推出“存在某条消息欺骗该检验”的概率至多为 。不同的消息可以在不同的随机串上成功。例如,令 与 均为两比特串,而检验恰在 时接受:每个固定的 通过的概率为 ,但对每个 都有某个 通过,所以“存在某条消息通过”的概率为 。必须对它们各自成功事件的并集加以界定,或者采用不同的论证。下面的证明通过放大,直到对所有可能消息取并集界变得可以承受为止。
例题 9.4.6
(图非同构挑战)
在下面的理想实验中,给定顶点数相同的两个图,亚瑟均匀地选取其中一个,施以一个均匀随机的置换,并把所得的图发送出去。梅林指出所选的是哪一个原图。如果这两个图不同构,不受限制的梅林可以辨别其同构类,并总能正确作答。如果它们同构,则无论选取哪一个,挑战的分布都相同,因此没有任何应答策略的成功概率能超过 。独立重复可使后一概率降到 以下;关于该分布与重复的论断,将在单独的交互式证明单元中详细证明。在这个特定的协议中,随机置换仅通过挑战图而公开;此例说明了交互式验证的动机,但其本身并不能确立上述公开硬币 AM 的定义。
本段首先描述理想的均匀置换实验。从 个置换精确均匀抽样,一般不能只用固定有限个公平比特。要得到有界时间的公平比特验证者,应使用图非同构单元中已证明的抽样器:其置换分布与均匀分布的全变差距离至多为 。对同构图以及任意证明者策略,单轮成功概率于是至多为 。给定任何先前交互记录,该界仍成立,因此两个使用新随机比特的轮次具有至多 的可靠性错误,完备性仍为一。不能把上述理想的 界直接当作近似抽样器的精确界。
为什么 MA 包含于 AM
下面的证明使用关于独立 – 变量的常用 Hoeffding 界:若它们的共同均值至多为 ,则其平均值达到 的概率至多为 ;当均值至少为 时,相应的下尾界同样成立。我们不加证明地引用这一集中不等式。独立性是针对某一固定消息的各次重复而言的。
定理 9.4.7
(在公开硬币之前进行放大)
。
证明
(证明)
设 ,其验证者为 ,消息长度为 。对于长度为 的输入,取 ,并采样 个独立的随机串 。定义 恰在 次计算 中严格多数接受时接受消息 。亚瑟在收到 之前就把全部 个随机串发送出去。它们的总长度与运行时间都是 的多项式。
若 ,选取一个 MA 见证 ,其原始接受概率至少为 。对于这个固定的见证, 个结果相互独立。由 Hoeffding 界,其接受次数至多为一半的概率至多为 。因此以大于 的概率,消息 有效;自适应的梅林当然可以发送它。
若 ,固定某条特定消息 。其原始接受概率至多为 ,因此它通过多数检验的概率至多为 。可能的消息恰有 条。由并集界,哪怕只有一条消息通过的概率至多为
这恰是针对在看到全部硬币之后才选取 的证明者的可靠性条件。我们并未假设不同消息的成功事件之间相互独立;并集界不需要这一点。由此得到的公开硬币协议证明了该包含关系。
证明透视
为什么重复次数必须随消息长度增长
证明中三项条件各只用一次。完备性只用于单个见证 ,所以“是”的情形不需要并集界。可靠性是逐条消息应用的,之后才把 个失败事件相加。唯一不寻常的一步是取 :每条消息的误差 必须胜过消息的条数 ,而 ,因为 。若 为常数,论证便会失效:取 时界为 ,只要 就超过 ,什么也说明不了。证明之所以能够闭合,是因为可靠性是在硬币之后才量化的:消息的存在性被吸收进并集之中,梅林针对 量身定制 的自由,只需付出 这个因子。
验证者使用严格多数,因此平局视为拒绝。在“是”实例上,下尾估计把平局计入可能的错误事件;在“否”实例上,上尾估计界定的是一个更大的、包含平局的事件。无需额外的平局裁决随机性。
放大所需的次数取决于见证的长度。常数次重复也许能降低每条固定消息的失败概率,但在硬币公开之后仍需尝试指数多条候选消息。上面所取的线性次数的重复使每条消息的错误概率指数级地小,足以抵偿全部 个候选。这是一个关于包含关系的证明,而不是这两个类相等或不相等的证明。
放大公开硬币协议
放大必须遵守消息的次序。在 AM 协议中,梅林看到全部公开硬币,并可以在各次重复之间协调其应答。若宣称梅林依赖于应答的接受事件相互独立,那将是错误的。相反,对于每个随机挑战,我们询问是否存在任何应答能通过它。这个问题仅依赖于挑战本身,因此所得的指示变量在相互独立采样的挑战之间是独立的。
命题 9.4.8
(AM 的多项式小误差)
设 具有完备性至少为 、可靠性至多为 的公开硬币 AM 协议。对任意取非负整数值的多项式 , 具有一个公开硬币 AM 协议,其在长度为 的输入上的两种错误概率均小于 。
证明
(证明)
取 个独立的随机串,并发送它们的串接。梅林为每个串返回一个候选应答,验证者恰在各个单独检验中严格多数接受时接受。对每个 ,若至少存在一个允许的应答能通过第 个随机串上的原始检验,则定义 。由于 固定且各挑战相互独立,无论梅林如何选取实际应答,指示变量 都相互独立。
在“是”实例上,。对每个好挑战占多数的序列,不受限制的证明者可以为每个好挑战选取一个通过的应答,因此放大后的验证者接受。在“否”实例上,。无论梅林采用何种联合应答策略,它都无法使坏挑战通过,所以要使多数检验被接受,就要求多数的 为一。Hoeffding 界将任一种错误界定为 。总通信量与运行时间仍为多项式。该证明不要求证明者所选的应答相互独立。
例题 9.4.9
(应答可以依赖于所有挑战)
设有两个公开挑战串 。证明者可以同时利用这两个串来选取其第一个答案,而不是仅利用 。如果对于 不存在任何允许的答案,这种额外的协调仍然无法使第一次检验通过。因此,“答案是否存在”这一指示变量为每一种协调策略提供了上界。在放大后的构造中,这些指示变量是独立采样的,尽管消息不必相互独立。
同样的区分也出现在包含关系的证明中。在那里,我们在采样一条长随机带之后,对消息取并集加以界定;而在 AM 放大的证明中,我们则为每个独立的挑战定义一个存在性事件,并对这些事件的多数加以界定。两种论证都从固定的输入出发,并始终保持证明者的完全自由度清晰可见。二者都没有用“重复总是有效”这类非正式论断来取代显式的完备性与可靠性量词。
加入更多回合的公开硬币与应答,只有在回合数增长时才会改变类。
通往推广的路径
有更多回合时会改变什么?
加入更多回合的公开硬币与应答,只有在回合数增长时才会改变类。
只有常数个公开硬币回合的协议,可以重新整理成这里研究的两消息形式,所以定义的是同一个类 AM。若允许回合数随输入长度按多项式增长,类就变成 PSPACE。这些是在别处证明的标准结果;改变的结构是亚瑟的硬币与梅林的消息之间交替的次数。
练习与解答
快速检查
(对于等式谓词 当且仅当 ,计算最佳固定消息的成功概率,以及硬币公开之后再应答的最佳成功概率。)
比较一个固定比特与一个已公开的比特。
解答 · 答案
每个固定的比特与一个均匀随机比特相符的概率为 。一旦该比特被公开,选取相同的比特即以概率一成功。
快速检查
(为什么 NP 验证者对“否”实例上的每一条可能消息都给出 MA 可靠性?)
回想 NP 可靠性对见证的要求。
解答 · 答案
NP 的可靠性表明,没有任何见证能使确定性验证者接受“否”实例。忽略随机性,则每条消息的接受概率均为零。
快速检查
(在包含关系的证明中,若 ,并集界中共有多少条长度为二的消息?所给的取法使用多少次重复?)
计算 与 。
解答 · 答案
共有 条消息。所选的重复次数为 ;并集界的上界估计为 ,小于 。
快速检查
(解释为什么在并集界论证中,不同消息的接受事件不必相互独立。)
在这个实验中,所有消息有什么共同之处?
解答 · 答案
它们都是针对同一个已公开的随机串序列来求值的。因此,一条消息的成功可能与另一条消息的成功相关。并集界只是把各自的概率界相加,在事件之间不独立时仍然有效。
快速检查
(如果验证者的随机串在消息之前就被公开,可靠性必须界定什么?)
对消息的量词现在处于什么位置?
解答 · 答案
它必须界定这样的概率:在公开随机串的取值上,存在任何一个允许的应答使验证者接受。这涵盖了每一种应答策略,包括在看到硬币之后才选取的策略。
快速检查
( 是否证明了 ?)
这证明了哪个方向的包含关系?
解答 · 答案
不。该包含关系说明每个 MA 语言都具有 AM 协议。它既没有证明反向包含,也没有给出区分二者的语言。