动机
多项式空间图灵(Turing)机可以有指数多个格局,因此其完整的转移矩阵太大,多项式时间的验证者无法将它写出。关键在于:通过请求精心选取的低次数概括量,来验证矩阵的某一个元素。反复平方把一段很长的计算化归为较短的计算,而随机直线检验则防止每一阶段的断言数目翻倍。
我们证明 ,并将其与量化公式配套单元中所证明的交互式证明的多项式空间上界相结合。证明使用 sum-check 协议,以及 sum-check 配套单元中的自适应可靠性定理;同时还使用阶为 的有限域的存在性、在显式表示的有限域中的多项式时间算术,以及标准的多项式空间图灵机格局。下面我们将说明验证者如何获得一个合适的显式域。该证明以上述所列基础为条件,而不依赖于任何未经证明的量子或计数定理。
固定语言 的一个确定性多项式空间判定器 ,采用单工作带、二元工作字母表的模型;标准的模拟与二进制编码保持多项式空间,并作为背景知识使用。对于输入 ,将其格局编码为 位串,其中 是 的多项式。添加一个接受汇点和一个拒绝汇点,各带一个自环,并将停机格局重定向至相应的汇点。添加足够多的未使用位,使其在每个有效编码中都固定为零,从而使有效格局数加上汇点数小于 。无效位串没有出边。从真正的起始格局可达的每个格局恰有一个后继,且机器最终到达某一个汇点。
布尔转移矩阵及其低次数延拓
设 为有限域 上的 矩阵,其元素 当且仅当 是 的指定后继时为一,否则为零。令
由于起始格局在每一步都有唯一的后继, 中以起始格局为指标的行恰有一个非零元素,其值为一,位于经过 步后到达的格局处。停机的计算在停机前不会重复任何格局,因此到时刻 时它已到达某个汇点。于是
这里用到了确定性:一般的非确定性图可以有许多条路径,即使存在一条路径,其条数也可能在模域的特征后变为零。
定义 9.3.1
(转移矩阵的多线性延拓)
对于位串 ,定义相等指示函数
在布尔(Boolean)点 处,当 时它取值为一,否则为零。将每个矩阵延拓为 个变量的多项式:
它在布尔点对上与 一致,并且对每个变量的次数至多为一。其总次数至多为 。该表达式有指数多项,因此对于 ,验证者不会将其展开。
例题 9.3.2
(一个两状态的确定性转移)
对于转移 ,,布尔矩阵为 。其多线性延拓就是 :对任一布尔源点,元素当且仅当目标位为一时取值为一。将该矩阵平方得到同一个矩阵。这个小例子展示了多项式如何在验证过程中无需逐项列出就能表示所有矩阵元素。
对于局部格局编码,基础延拓 可以被高效地求值。使用独热(one-hot)的状态位与头位置位、二进制的带格位,以及为两个汇点选取的、位于普通格局编码之外的互异固定编码。在每个有效的普通格局中,完整的状态以及每个完整的头位置模式都是独热的,且每个未使用位均为零。枚举多项式数量的组合:当前非停机状态、输入头位置、工作头位置与所扫描的工作符号。对于每个合法的转移情形,将固定完整源与目标的状态/头位置模式、所有未使用位以及被改变的带格的指示函数相乘。对于每个未改变的带格,设其源位为 、目标位为 ,使用多线性相等因子 。每种情形是一个乘积,其中每个源位或目标位至多出现在一个因子中。
从停机格局到规范汇点的转移单独处理:固定完整的停机源控制模式与头位置模式以及未使用的源位,但不约束源的带位;再乘以目标的整个固定汇点编码的指示函数。在这种情形中不施加未改变带格的相等条件,因为规范汇点可以有不同的带内容。每个汇点自环由其完整源编码与目标编码的指示函数之积表示。这些停机与汇点情形与非停机情形互不相交;而后者在布尔编码上也互不相交,因为当前状态、头位置与所扫描的符号决定了所属情形。无效编码不匹配任何情形。该和式有多项式数量的情形,是一个多项式大小的电路,对每个源位和目标位均为多线性,并且在布尔点对上与 一致。由布尔立方体上多线性插值的唯一性,它与 相等。
关于唯一性的论断:若两个多线性多项式在每个布尔输入上取值一致,则将二者相减,并对变量个数作归纳:把差写成 ,其中两个系数均不含 。在 与 处求值,使两个系数在较小的布尔立方体上都为零;由归纳假设,它们是零多项式。因此验证者能够对所需的基础延拓求值,而不仅仅是对一个与之在布尔点上取值相同的任意多项式求值。
例题 9.3.3
(非布尔输入处的相等性)
在特征二下,一位的多线性相等多项式为 。它在布尔数对 处等于一,在 处等于零。然而在 上,,它既不是零也不是一。验证者在域上的点处计算多项式;它不会假装每个中间值都是布尔真值。这种行为是预期之内的,也正说明了为什么必须指定多线性延拓。
作为 sum-check 的一次平方步骤
对于位串 与域向量 ,指示函数 已在上文定义。当 被换成域向量 时,对 使用其多线性插值:
对于 的一个被声称的值,矩阵平方恒等式给出
这里在求和过程中 是固定的域向量。将该表达式中的布尔串替换为变量向量,并使用 ,由此把被加项定义为域变量 的多项式。
命题 9.3.4
(平方被加项的单个变量次数很小)
该被加项是 个域变量 的多项式,对每个单独变量的次数至多为二。因此,以次数界二运行的 sum-check 把关于 的断言化归为关于该被加项在一个随机三元组 处的断言。
证明
(证明)
每个 出现在一个相等指示函数因子中,并出现在多线性多项式 中,因此次数至多为二。每个 同理。每个坐标 在两个多线性矩阵因子中各出现一次,次数同样至多为二。该恒等式由展开 的定义,并在布尔下标上代入 得到。即使验证者无法直接展开该形式低次数多项式,sum-check 定理仍然适用于它。
在最终的 sum-check 点处,验证者可以计算两个相等指示函数因子,但尚不能对 求值。它向证明者索取两个被声称的值
并检验它们的乘积乘以已知的指示函数因子是否等于最终的 sum-check 断言。这两个值是不被信任的。如果在每一层平方处都分别验证它们,就会产生一棵二叉的断言树,因此我们把二者合并为一个断言。
在随机直线上合并两个断言
设 与 为 中的两个点。证明者发送一个次数至多为 的单变量多项式 ,声称
验证者检验 与 ,选取一个新的、在 中均匀的 ,并递归地检验单一断言 。系数列表长度超过 的消息被拒绝。真实的直线限制的次数至多为 ,因为 是 个变量的多线性多项式。
命题 9.3.5
(随机直线断言化归)
若 中至少有一个为假,且端点检验通过,则递归断言仍然为真的概率至多为 。
证明
(证明)
所发送的多项式与真实的直线限制的次数都至多为 。若端点检验通过而某一端点值为假,则两个多项式在该端点处取值不同,因此二者不恒等。它们的非零差在 中至多有 个根。证明者在看到新的均匀 之前就选定了 ,所以即使以整个先前的对话记录为条件, 等于真值的概率至多为 。
例题 9.3.6
(直线上的一个假端点)
对于 上的玩具多线性多项式 ,设 ,。真实的直线限制为 。若证明者谎称第二个端点值为三,则任何满足 的所发送的 都不同于 。若允许的次数为二,则这个差至多在两个域元素处为零。随机挑战可能错过某个特定的错误,但在所述次数界之下,它不可能在每一个挑战处都掩盖一个假端点。
完整的验证协议
验证者从断言 出发,对 依次应用平方 sum-check,随后应用随机直线化归。在第零层,它直接对 的多项式大小电路求值。所有证明者消息的次数界都经过显式检验。
定理 9.3.7
(多项式空间语言具有交互式证明)
。
证明
(证明)
选取大小 的域。获得显式域的一种确定性方法是:取 ,枚举 次的首一二元多项式直至找到一个不可约多项式,并通过枚举可能的首一因子来检验各候选。候选至多有 个,可能的因子至多有 个,因此这一暴力构造关于 是多项式的。每个正次数的不可约多项式的存在性,由有限域的构造以及乘法生成元的存在性得出;这些事实在有限域配套单元中证明。该商环表示 ,支持多项式时间算术,且一个均匀的 位串可对域元素进行均匀采样。
若 ,则所有被声称的值都可以诚实地选取。布尔起始元素为一,每个矩阵恒等式与每个 sum-check 都是精确的,并且直线限制通过两个端点检验及每一个挑战。验证者以概率一接受。
若 ,则初始断言为假。在第 层,sum-check 使用 个变量且单个变量次数为二,因此其自适应可靠性论证把一个假的求和断言变为真的最终被加项断言的概率界定为 。若最终断言仍为假,而证明者的乘积检验通过,则 中至少有一个必为假:若二者都正确,则它们的乘积与已知的指示函数就会给出被加项的真值。若某个指示函数因子为零,则一个假的非零最终断言根本无法通过该检验。
在存在假端点时,直线化归定理把下一个递归断言变为真的概率界定为 。以每一个先前的对话记录为条件,在这一层逃脱假断言的概率因此至多为 。共有 层。对假断言首次变为真的那一层作并集界,得到总概率至多为 。若没有发生这样的逃脱,验证者的直接基础求值将拒绝。因此,对于否例,每个证明者被接受的概率至多为 。
共有 层,每层有 轮 sum-check 和一次直线检验。次数为二的消息有三个系数,直线消息至多有 个系数。所有域算术、基础求值、通信与随机比特的生成都只使用多项式资源。证明者不受限制,可以计算指数大的矩阵元素以及诚实消息的系数。这就是 的一个交互式证明。
证明透视
错误预算与断言数目从何而来
确定性只在起点用一次:它使 等于零或一,而不是一个可能在域中相互抵消的路径条数。唯一不显然的一步是直线归约。每次平方产生两个断言: 关于 , 关于 ;若分别检验,第 层会剩下 个断言,于是第零层有 个断言,验证者就需要指数时间。把它们合并到一条直线上,每层恰好只剩一个断言。错误预算是逐项相加的:sum-check 至多 ( 轮、次数为二),随机直线至多 ,所以每层为 ;只要 , 层合计为 。论证在第零层闭合:若断言在该处仍为假,就会与直接算出的 的值比较而被拒绝。若域小得多,例如 ,上界就会超过 ,什么也无法保证。
常见错误
(为什么论证使用确定性格局图)
矩阵元素在所选的域中对路径计数。对于非确定性图,接受路径的条数可能被特征整除,因而即使存在接受路径,它在域中也等于零。例如,若起始格局有两个后继,且二者在下一步都移向接受汇点,则从起始到汇点有两条长度为二的路径,而在特征为二的域中 。确定性的空间受限判定器从起始格局出发只有唯一的计算;吸收汇点使相关元素恰好为零或一,从而避免了这种相消问题。
IP 的多项式空间上界在量化公式配套单元中被独立证明,方法是枚举公开的对话记录并计数与之一致的私有随机带。将两个包含关系结合,得到 。此处的证明使用局部格局矩阵构造与 sum-check;它不依赖于另一条 TQBF 到 IP 的算术化路线。
练习与解答
快速检查
(为什么对于编码后的确定性计算, 的起始行恰有一个非零元素?)
从起始格局出发沿计算走 步。
解答 · 答案
每个可达的格局只有一个后继。对步数作归纳,得出从起始格局出发恰有一条路径,其矩阵元素为一;吸收汇点在停机后保持唯一性。
快速检查
(为什么基础多项式必须是多线性延拓,而不能只是任何在布尔点上取值相同的多项式?)
随机直线这一步依赖哪个次数界?
解答 · 答案
随机直线的限制必须有已知的次数界,至多为 。任意一个取值相同的多项式可能含有在布尔方体上为零的高次项,使根的个数上界失效。
快速检查
(平方被加项对每个 的单变量次数界是多少?)
数一数 出现在多少个因子中。
解答 · 答案
至多为二: 出现在两个因子中,而每个因子对该变量都是多线性的。
快速检查
(为什么验证者不分别递归检验 与 ?)
经过 层之后会有多少个断言?
解答 · 答案
分别递归检验会在每个平方层使断言数加倍。随机直线检验把两个端点断言归约为一个需要递归检验的断言。
快速检查
(若其中一个端点断言为假,为什么证明者所发送的直线多项式不同于真实的直线限制?)
在假端点处比较两个多项式。
解答 · 答案
所发送的多项式通过两个端点检验,所以在任何被谎称的端点处都与真实的限制不同。在一点上不同,就说明两个形式多项式并不相同。
快速检查
(当 时,对于虚假的初始断言,经过 层之后得到的上界是多少?)
把各层的误差相加,并使用并集界。
解答 · 答案
并集界给出至多 。