一个简短的证明凭据(certificate)是一个静态对象。而对话则允许验证者在收到信息之后,另行选择一个全新的挑战。挑战的设计必须使得诚实的证明者能够作答,而不诚实的证明者无法充分预测该挑战,从而不能使一个错误的断言具有说服力。图非同构给出了一个具体的例子:验证者可以高效地生成一个经过伪装的图,即使它自己并不知道如何单独识别该图的来源。
两种角色与两种概率
定义 9.1.1
(语言的交互式证明)
一个交互式证明系统包含一个在多项式时间内运行的随机化验证者 ,以及一个没有计算时间限制的证明者 。它们在公共输入 上交换消息,最后验证者接受或拒绝。对于语言 ,完备性要求:对每个 ,存在某个证明者使 以至少 的概率接受。可靠性要求:对每个 ,每一个证明者都至多使 以 的概率接受。概率取自验证者的随机选择;若证明者使用随机性,则也取自证明者的选择。类 由具有这样的多项式时间验证者且消息数为多项式个的语言组成。
这些量词承担着不同的作用。完备性允许针对整个语言选定一个诚实的证明者,而不是验证者能够执行的某个高效算法。可靠性则是对抗性的:它必须对每一种可能的证明者策略都成立。验证者的计算以及整个通信记录必须受多项式界限制;证明者为了决定发送何种消息,可以求解计算上困难的问题。为防范恶意证明者,验证者至多读取规定的多项式消息长度再加一位;消息超长时拒绝。在评估成功概率时,输入是固定的。这是一个最坏情形的要求,而不是对图对取平均。
非确定性证明凭据是这一图景的特例:证明者发送一个证明凭据,验证者对其进行确定性检验。只有当验证者的私有选择会影响所需的应答时,交互才是有用的。公开通信并不意味着对证明者隐藏的选择必须在使用之前被披露。
作为单消息对话的证明凭据
该定义本身已经包含了与非确定性验证的一个有用比较。与其把证明者当作一个无法解释的预言机,不如证明这一包含关系:一个 NP 见证给出证明者的消息,而确定性验证者仍然负责最终的判定。
命题 9.1.2
(NP 包含于 IP)
中的每一个语言都有一个交互式证明,具有完美完备性与完美可靠性,仅使用一条证明者消息,且验证者是确定性的多项式时间验证者。
证明
(证明)
对给定的 NP 语言,选取一个多项式时间验证者 以及多项式的证明凭据长度界。证明者发送一个候选证明凭据;若它过长,交互式验证者拒绝,否则在输入与该证明凭据上计算 。若输入属于该语言,则存在某个短的证明凭据被接受,所以诚实的证明者发送它,接受是必然的。若输入不属于该语言,则没有任何证明凭据被接受,无论证明者采取何种策略,所以拒绝是必然的。验证者使用多项式时间。这就证明了该包含关系;它并未证明每个交互式证明都有短的静态证明凭据。
例题 9.1.3
(小团的一个证明凭据)
设输入图的顶点为 ,边为 ,所声称的团的大小为 。证明者发送列表 。验证者检查这些项是互不相同的顶点,然后对照输入检查三个顶点对 ;它们都是边,所以验证者接受。如果该图不含大小为 的团,则每个可能的三顶点列表要么重复了某个顶点,要么包含一条不存在的边。可靠性论证针对的是所有可能的消息,而不仅仅是诚实的证明者碰巧发送的那个列表。
图同构与重新标号
定义 9.1.4
(图同构与图非同构)
两个有限简单图 与 是同构的,如果存在它们顶点之间的一个双射,同时保持邻接与不邻接关系。当两者都有 个顶点时,我们可以用 来标记每个顶点集;对这些标号作一个置换会产生一个重新标号的图。图非同构,在此缩写为 GNI,是由不同构的有限简单图对所构成的语言。
顶点数不同的图对显然是不同构的,可以立即接受,所以下面的协议针对的是大小相等的图。大小为零的图对由两个空图构成,因此是同构的;验证者可以立即拒绝。
证明者可以看到两个图。验证者选取一个均匀随机的比特 以及一个与之独立的、对 个标号均匀随机的置换 ,发送 ,并询问它来自哪一个输入图。如果回答等于 ,验证者接受。对于均匀置换的高效实现,使用标准的随机置换过程;在下面的概率论证中采用理想的均匀选择。由公平比特实现的有界误差版本需要注意精确采样的问题,也可以改用一个足够精确的多项式时间采样器,并把误差计入可靠性界中。
例题 9.1.5
(一条路径还是一个三角形?)
设 为三个顶点上的路径, 为三角形。重新标号改变的是顶点的名字,而不是边数。路径总是有两条边,三角形有三条边,所以即使是验证者也可以通过数边来识别来源。这说明了协议中的各条消息,不过一般协议的要点在于:对任意输入图,高效的验证者并不需要知道某个简单的区分不变量。
以有界运行时间对置换进行采样
理想的均匀置换使主要思想易于理解,但一个使用固定数目公平比特的多项式时间验证者必须实现它自己的选择。对于大小不是 2 的幂的范围,一般无法由固定数目的公平比特精确地产生该范围内的均匀随机整数。因此我们明确地控制近似误差。
命题 9.1.6
(有界比特采样器接近均匀)
对每个正整数 ,存在一个采样器,它使用多项式个公平比特并在多项式时间内运行,其在 个对象的置换上的输出分布与均匀分布在全变差距离意义下至多相差 。
证明
(通过耦合各次选择来证明)
使用通常的交换构造:对 ,从 中选择一个下标,并将其与当前位于位置 的项交换。如果这些选择相互独立且均匀,则 种选择序列中的每一种概率为 ,并给出不同的置换,所以输出是均匀的。
设 是满足 的最小整数。要在大小为 的范围内选择一个下标,抽取 个公平比特以构成从 到 的一个均匀整数,取其模 的余数,再加 。每个下标出现的次数为 的下取整或上取整。其概率与 相差小于 ,所以这一次选择与均匀分布的全变差距离至多为 。把该选择与一个理想的均匀选择耦合,使它们不一致的概率至多为 。对所有步骤,由并集界得到不一致的概率至多为 。如果没有任何一步不一致,则输出的置换一致。因此输出分布在全变差距离下相差在 之内。该采样器至多使用 个比特和多项式时间。
对于一个同构的图对,把实际的采样器与理想的采样器耦合。对任何固定的证明者策略,每当所采样的置换一致时,交互记录与接受结果就一致。猜对的理想概率为 ,所以实际概率至多为 。耦合可以在任意先前的通信记录的条件下重新进行。因此两轮新的重复的可靠性至多为 ,而完备性仍为 。这就证明了该协议满足固定公平比特模型,而不是假设存在精确的非二进制随机选择。
完备性:诚实的证明者可以识别轨道
设 与 不同构。 的一个重新标号 与 同构,且不可能与另一个输入图同构:否则,两个同构的复合将表明 。一个无界的证明者可以枚举置换并判定哪一个图与 同构。它必然返回 。因此该协议对不同构的输入具有完美完备性。
“无界”一词确实起着实质作用。诚实的证明者可以检查全部 个置换;我们并不假设存在针对该搜索的多项式时间算法。验证者仅仅对置换进行采样、对图重新标号,并把一个比特的回答与自己的私有比特进行比较。
可靠性:挑战隐藏了它的来源
命题 9.1.7
(单轮图非同构协议)
对于大小相等的输入图,上述协议在诚实的证明者下以概率 接受每一个不同构的图对。如果输入图同构,则在理想均匀采样器下,任何证明者,无论多么强大,只要它总是发送一个比特,被接受的概率恰好为 。此处所述的有界比特实现与重复给出了 GNI 的一个交互式证明。
证明
(为什么同构的图给出相同的分布)
设对某个固定的置换 有 。如果 ,所发送的图是 。如果 ,则是 。乘以固定的置换 是有限置换群上的一个双射,所以只要 均匀分布, 也均匀分布。因此 的分布对 的两个取值是相同的。
证明者看到输入和 ,但 没有提供关于公平比特 的任何信息。对于任何基于该视图的固定应答规则,应答等于 的概率为 。对证明者的任何私有随机性取平均后,同样的结论成立。非比特的应答可以直接被拒绝,在这种情况下概率至多为 。
证明透视
为什么挑战不带任何信息
不显然的一步,是比较整个带标号图的分布,而不是边数之类的不变量。假设 恰好只用在一处:它把 时的挑战变成 。乘以固定的 是置换群上的双射,所以均匀的 仍然均匀,两个挑战分布因而相同。另有两项要素同样重要。置换 与比特 是独立选取的,因此 的分布不依赖于 ,就表示 与 独立。并且 在证明者作答之前一直保密,所以证明者的应答是 、输入及其自身随机性的函数,这些都不依赖于 ;它与 相符的概率恰好是 。
整个论证无需对证明者的运行时间作任何限制。若 不均匀,两个 的分布就可能不同,论证随即失效;若 被泄露,应答就成了 的函数,论证同样失效。
这一论证是信息论意义上的:没有用到对不诚实证明者运行时间的任何限制。重要的等式是带标号图的整个分布之间的等式,而不仅仅是边数或任何某个图不变量之间的等式。即使许多置换产生相同的带标号图,乘以 也会把在两种情形下产生该图的置换配成对,且重数保持不变。
反例模式
没有随机重新标号,挑战会泄露其来源
假设验证者省去置换,直接发送 。取 ,令 只有一条边 , 只有一条边 。这两个图是同构的,同构由互换 与 的置换给出,因此该输入不属于 GNI。然而作为带标号图,它们并不相同,所以看到 的证明者可以立即读出 ,并以概率 被接受。可靠性证明需要均匀的 :重新标号之后,无论所发送的图来自哪一个输入,它的分布都相同。
重复与自适应策略
在理想均匀采样下,独立地运行两次挑战,仅当两次回答都正确时才接受。完备性仍为 ,而可靠性至多为 ,低于所要求的 。作弊的证明者可以利用整个先前的通信记录来选择它的下一个应答。然而,在该通信记录的条件下,下一个比特和置换是全新的,新挑战的两个条件分布仍然相同。它的条件成功概率至多为 。将两个条件界相乘得到 ;类似地, 轮给出至多 的可靠性。
如果验证者在证明者作答之前就披露 ,则这一论证会被破坏。挑战图是公开的,但随机的来源比特在应答之前一直是私有的。把这两部分信息分开,是核心的设计选择。
例题 9.1.8
(一个重新标号的副本没有给出关于该比特的证据)
设两个输入都是同一个带标号的四圈(four-cycle)。某个特定的重新标号 可能由若干个置换产生,因为该圈具有对称性。尽管如此,对于每个在 时产生 的置换,同一个置换在 时也产生 。条件分布一致,看到 并不会改变任一比特的先验概率 。对于不同但同构的带标号副本,论证使用固定的重新标号 来得到同样的配对。
常见错误
(诚实的证明者不足以说明可靠性)
说明诚实的证明者能够作答,只是完备性。如果两个图同构,作弊的证明者可以使用任何策略,包括针对整个通信记录量身定制的策略。可靠性的证明必须说明,没有任何这样的策略能够从两个相同的分布中恢复出一个隐藏的比特。
这确立了什么,没有确立什么
该协议证明了 GNI 属于 。它并没有证明 GNI 不在 中,也没有证明图同构没有多项式时间算法,或者 严格大于 。重要的定理 需要额外的工具,此处不予证明。这些区分之所以重要,是因为一个包含关系或一个成功的协议是一种正面的构造;它并不会自动确立复杂度类之间的分离。
练习与解答
快速检查
(为什么不同构的输入图给出的可能挑战图的集合是不相交的?)
假设有一个图同时属于两个集合。
解答 · 答案
同时属于两个集合的图将同时与两个输入图同构。把一个同构与另一个同构的逆复合,将使两个输入图同构,这与假设相矛盾。
快速检查
(假设输入图同构。即使证明者是自适应的,连续正确回答三个全新的独立挑战的最大概率是多少?)
把各个条件界相乘。
解答 · 答案
在理想均匀采样下,界为 :在任何先前的通信记录之后,下一个全新的挑战对于任一隐藏比特仍具有相同的分布。使用上述有界比特采样器时,相应的界为 。
快速检查
(如果验证者把它隐藏的比特与重新标号后的图一起发送给证明者,会出什么问题?)
想想谁会得知这个比特。
解答 · 答案
证明者可以对每个输入都返回所提供的比特,包括同构的图对。于是验证者以概率 接受错误的断言,违背了可靠性。