动机
量化布尔(Boolean)公式描述一种博弈:存在量词的选择试图使公式为真,而全称量词的选择则对其发起挑战。对这一博弈求值可能需要探索指数多种对局,但深度优先搜索可以重复利用内存。反过来,一个紧凑的量化公式可以描述穿过指数规模格局图的可达性。这两个方向使得真量化布尔公式成为多项式空间的一个自然完全问题。
定义 3.3.1
(量化布尔公式与 TQBF)
量化布尔公式由布尔变量、联结词以及取值范围为 的量词 构成。闭公式没有自由变量。设 TQBF 为在某种标准有限编码下所有为真的闭量化布尔公式构成的语言。我们允许嵌套的量化公式,而不仅限于已经是前束范式的公式。标准的变量重命名和语法编码可以在多项式时间内完成;下面的证明并不依赖于将量词移过任意否定。
求值只需多项式空间
命题 3.3.2
(TQBF 属于 PSPACE)
TQBF 可由确定性多项式空间机器判定。
证明
(以复用栈作递归求值)
递归地对公式求值。在存在量词处,先将变量设为零对其余公式求值,然后在必要时再将其设为一求值;若任一求值为真,则返回真。在全称量词处,仅当两次求值均为真时才返回真。对于布尔联结词,先对其各个运算对象求值,再组合所得真值。必要时对变量重命名,使各个作用域没有歧义。
该机器存储当前的变量赋值、指向输入公式的一个指针,以及一个深度至多为公式长度的递归栈。每个栈帧使用多项式个比特,且已结束的递归调用会重复利用其工作空间。总空间是输入长度的多项式。递归调用的次数可能是指数多个,因此这是一个空间界,而不是多项式时间界。
例题 3.3.3
(一个两轮量词博弈)
命题 为真:看到 之后,选择 即可。交换顺序得到 ,它为假,因为一个固定的比特 不可能既等于零又等于一。递归求值器会检验全称变量的两个取值,并在第二个分支中重复使用同一块内存。这个例子说明了为什么后面的选择可以依赖于前面的选择。
紧凑地描述指数长度的可达性
设有向图的顶点由 位串编码,并且存在多项式大小的布尔公式 ,用以判定所编码的两个顶点之间是否有边。该图最多可有 个顶点。定义量化公式 ,它恰在存在一条从 到 、至多含 条边的路径(walk)时为真。其基础情形为
等式情形允许长度为零的路径,当一次拆分中的某一半比另一半短时,这一点很有用。
显而易见的递推式 会重复前一个公式,可能使其书写长度关于 呈指数增长。我们用一个全称选择位来避免这种重复。设 断言:当 时 ,当 时 。它是一个大小为 的布尔公式,用于逐位比较对应的比特。定义
其中 是 位的块, 是一个比特。每个新约束的变量都经过重命名以避免变量捕获。
定理 3.3.4
(选择位递推)
对每个 ,公式 恰在存在一条从 到 、至多含 条边的有向路径时为真。其书写长度是 、 以及边公式大小的多项式。
证明
(选择位公式的等价性与大小)
基础情形允许零条边的路径或一条边。对于归纳步骤,假设存在长度至多为 的路径。在把它拆成两条长度至多为 的路径的位置处选取 ;允许其中一半为空。对于 的每个取值,选取与其中一半相对应的、被唯一确定的二元组 。由归纳假设,递归公式为真,因此 为真。
反之,若 为真,则其所选的 必须对 的两个取值都成立。选择位迫使递归的二元组在取零时为 ,取一时为 。归纳假设对每一半给出一条长度至多为 的路径。将它们连接起来,得到一条长度至多为 的路径。
所显示的公式只含 的一份拷贝。除标准的变量名编码开销外,每一层包装增加 个符号。因此,经过 层之后其大小是 以及基础边公式的多项式。交替出现的选择位以量词选择取代了语法上的重复;这并不是说对该公式求值只需多项式时间。
证明透视
选择位如何使公式保持简短
朴素的递推式 含有两份 ,所以长度每一层都加倍,经过 层后达到基础公式大小的 倍。选择位公式只含一份 ,并把全称位 所选出的数对 交给它,因此长度每层只增加 。等价性的证明在两个方向上都用到量词的排列方式:中点 在 之前确定,所以同一个 必须同时适用于两半; 是全称的,所以两半都是真正需要的。存在量词 并非真正的选择,因为对每个 ,选择位公式已把它们强制确定。这里没有任何东西使求值变快:公式描述的是一个指数长的搜索,多项式空间的求值器仍须把它逐一走完。
例题 3.3.5
(一条两边的路径)
对于含有边 与 的图,公式 可以选取中点 。若全称选择位取零,则被迫的递归查询是 ;若取一,则是 。二者皆为真。若只存在 ,且没有其他通向 的路径,则第二种选择位的取值会暴露缺失的那一半,从而拒绝该中点。
常见错误
(全称选择位并不选取中点)
中点 是在全称位之前由存在量词选取的。它必须对两半都成立。如果把量词次序颠倒为 ,两个分支就可以使用互不相关的中点,于是两条短路径未必能够连接。量词的位置是可达性证明的一部分。
反例模式
调换中点与选择位的量词
假设把 的排列改为 ,使中点可以依赖选择位。取一个边为 、、、 的图,即两条互不相连的路径,所以从 不能到达 。对 ,调换后的公式需要一个 ,使从 到 有至多两条边的途径, 可行。对 ,它需要一个 ,使从 到 有至多两条边的途径, 可行。因此调换后的公式 为真,尽管 不可达。若采用正确的次序,单个 必须同时能在两条边内从 到达,并能在两条边内到达 ;前一个集合是 ,后一个是 ,没有这样的 ,公式为假,这正是应有的结果。
TQBF 的 PSPACE 困难性
定理 3.3.6
(TQBF 是 PSPACE 完全的)
PSPACE 中的每个语言都可通过多项式时间多一归约(many-one reduction)归约到 TQBF。结合成员性,TQBF 在这类归约下是 PSPACE 完全的。
证明
(编码空间受限的计算)
固定语言 的一台确定性多项式空间判定机 。对于长度为 的输入 ,用 个比特编码一个完整的格局,其中 为多项式:包含有限状态、输入头位置、工作头位置以及多项式有界的工作带内容。必要时增大 ,以保留一个互异的接受汇点。候选比特串至多有 个。实际的起始格局与汇点都有可由 计算出的显式编码。
多项式大小的布尔公式 检验 是否是 的合法单步后继,并且每个接受格局都有一条通向新汇点的边。为说明其大小的界,枚举多项式多种可能的头位置以及有限多个状态与转移规则。对每种情形,比较相关的输入符号,要求规定的状态与头部更新成立,要求唯一被改变的工作带单元具有其新符号,并要求所有其他工作带单元保持不变。这些多项式大小的情形的析取给出该公式;无效的候选编码没有出边。输入 被硬编码进此构造之中。
由于 会停机,它接受 当且仅当汇点可从其起点到达。任何可达的顶点都有一条从起点出发的简单路径:删去重复顶点之间的环即可。由于候选顶点至多有 个,通往汇点的简单路径所用的边数少于 。由选择位定理,闭量化公式 恰在此种情形下为真。因为 与 都是多项式,所以它的大小与构造时间都是 的多项式。因此 当且仅当所产生的量化公式为真。
该归约包含了语法上可能但不可达的格局。这并不会产生虚假的接受路径:从可达格局出发的每条边都是真实的转移,所以对路径长度作归纳可知整条路径都处于真实的计算之内。新增的汇点允许存在多个接受格局,而无需公式去猜测最终会到达哪一个。
在多项式空间中模拟交互式证明
定义 3.3.7
(交互式证明)
交互式证明包含一个多项式时间的随机化验证者和一个不受限制的证明者。完备性要求存在某个证明者,使验证者以至少 的概率接受是实例;可靠性要求在否实例上,每个证明者使验证者接受的概率至多为 。对于每个对话记录,验证者的时间、随机比特数、消息条数以及允许的消息长度都有多项式上界。这包括其私有随机性。
定理 3.3.8
(交互式证明包含于 PSPACE)
。
证明
(枚举公开对话记录)
固定一个输入。把验证者的随机带填充到固定的多项式长度 ,并把交互填充到固定的多项式轮公开消息,提前终止后用显式填充补足。证明者能看到验证者的公开消息,但看不到其私有随机带。我们枚举的是公开对话记录的树,而不是向证明者泄露隐藏随机选择的树。
在证明者消息节点处,枚举所有允许的下一条消息,并取各后续计数中的最大值。在验证者消息节点处,对所有可能的下一条公开消息及终止结果,将其后续计数求和。在叶子处,对话记录确定了所有证明者消息与所有验证者的公开消息。枚举全部 条私有随机带,用这些证明者消息重放确定性的验证者,并统计那些恰好产生所记录的公开对话记录且接受的随机带的条数。这个计数可用 个比特表示。无效或不一致的对话记录贡献为零。
该递归计算从每一段公开历史出发所能达到的接受随机带数目的最大值。验证者消息的各分支对相容的私有随机带作划分,所以它们的计数相加。证明者的下一条消息是依据公开历史选取的;在该节点取最大值就代表了每一种确定性策略,同时不允许其依赖于隐藏的随机硬币。随机化的证明者不可能做得更好,因为它的选择是各确定性后续的平均。由于对话树有限,在每个公开历史处选取一条使其最大的消息,就得到一个确定性的最大化策略。
每个递归帧存储到目前为止的公开对话记录、一个消息枚举计数器,以及一个 位的累加器或最大值。递归深度是多项式的,叶子处对验证者的模拟使用多项式空间;已结束的分支重复利用其内存。分支数与随机带的条数可能是指数多个,但同时存储的量是多项式的。在根处,将接受随机带数目的最大值在概念上除以 ,并与 比较。完备性使其在是实例上至少为 ,可靠性使其在否实例上至多为 。因此确定性多项式空间机器可以判定该语言。
例题 3.3.9
(先最大化再平均)
设证明者先发送一个比特 ,随后验证者掷一枚均匀硬币得到比特 ,并恰在 时接受。每个固定的消息成功的概率为 ,所以最大值为 。若验证者改为在消息之前公开 ,证明者就可以选择 ,最大值变为一。基于公开对话记录的求值器遵循这一次序:它只在证明者实际看到的消息之后取最大值,而在叶子处统计私有随机带。如果 是保密的,那么在得知其值之后再分别取最大值,就会错误地赋予证明者隐藏的信息。
反向包含 需要为某个 PSPACE 完全问题(如 TQBF)给出一个交互式协议。配套的 sum-check 单元证明了一个低次数求和协议,但要把量化公式变成这样的交互式证明,还需要额外的算术化与次数控制论证。这些在此处并未证明。因此,本单元确立的是 TQBF 的完全性与 IP 的上界,而不是完整的等式 。
练习与解答
快速检查
(为什么深度优先的量化公式求值器尽管要探索指数多种赋值,却只需多项式空间?)
解答 · 答案
它只存储当前赋值与递归栈,并在每个分支结束后重复利用这部分空间。分支的数目影响时间,但不必影响同时存储的量。
快速检查
(在选择位递推中,为什么中点必须在全称选择位之前选取?)
解答 · 答案
同一个中点必须对选择位的两个取值都能拆分路径。若较晚选取,则可能允许互不相关的中点,也就无法保证得到连接后的路径。
快速检查
(如果一个图至多有 个被编码的顶点,那么简单路径长度的一个充分界是什么?)
解答 · 答案
可达的顶点有一条至多含 条边的简单路径;允许 条边是一个方便的充分界。
快速检查
(为什么选择位递推的书写大小是多项式的,而朴素的双拷贝递推则可能不是?)
解答 · 答案
每层选择位包装只含前一个公式的一份拷贝,并只增加多项式个符号。朴素递推在每一层含有两份拷贝,所以其书写大小可能反复翻倍。
快速检查
(在交互树模拟中的证明者节点处,为什么取最大值就足够了?)
解答 · 答案
对每条可能的消息,其后续都有一个明确的接受概率。随机化的选择是对这些值取平均,不可能超过它们的最大值;由于消息集合是有限的,所以存在使其最大的确定性选择。
快速检查
( 的证明是否确立了反向包含?)
解答 · 答案
没有。反向需要为某个 PSPACE 完全语言给出单独的交互式协议,其中包括此处未证明的算术化与次数控制工作。