动机
判定算法只回答满足赋值是否存在;学生往往还想得到赋值本身。对于 SAT,这两个任务联系紧密:询问一个部分变量已固定的公式是否仍然可满足,就能每次揭示见证的一位。只要见证长度受多项式界限制,同样的想法对每个多项式时间可验证的关系都适用。
把“是”与“否”两种条件结合起来,会得到另一个有用的类。一个公式可以至少有一个满足赋值,同时又不存在两个不同的满足赋值。第一个断言有 NP 见证,第二个则是 coNP 断言。明确区分这两种角色,可以避免把“恰有一个”误当作普通的 NP 证书。
定义
定义 2.4.1
(多项式平衡的 NP 关系及其判定语言)
多项式平衡的 NP 关系是一个确定性多项式时间谓词 ,并附带一个固定的多项式 ,使得有效见证可以取为恰好 位。较短的表示可以通过长度标记加填充来编码,验证者负责检查编码并忽略填充部分。其判定语言为
搜索过程必须对每个 输出一个有效的 ;对于没有见证的输入,我们会明确说明它必须报告失败,还是可以返回任意字符串。
定义 2.4.2
(前缀语言)
的前缀语言为
换言之,当部分见证 仍可补全为有效见证时,。
前缀语言属于 NP:剩余的后缀 是多项式长度的见证,验证者检查长度并计算 。过长的无效前缀一律拒绝。我们使用配套的 Cook–Levin 笔记中的结论:SAT 在多项式时间多一归约下是 NP 完全的。
定理
定理 2.4.3
(由前缀判定进行搜索)
对每个多项式平衡的 NP 关系,带有 SAT 预言机的确定性多项式时间机器在见证存在时可以输出一个有效见证,在见证不存在时报告失败。在把前缀问题以多项式时间归约为 SAT 之后,它至多使用 次预言机查询。
该定理并不假设任意的判定语言 本身能够回答每一个前缀问题。预言机解决的是前缀语言,并借助前缀语言到 SAT 的 NP 归约。在把熟悉的 SAT 过程推广到其他关系时,这一区别十分重要。
证明
证明
(逐位固定见证)
首先查询 是否成立,其中 是空前缀。若不成立,则不存在见证,机器报告失败。否则维持一个至少有一个有效补全的前缀 。若 ,查询 是否成立。答案为是时,在 后追加 ;答案为否时,追加 。
该不变式得以保持。若存在以 开头的有效补全,则第一个分支选中这样的前缀。若没有任何补全以 开头,则旧前缀仍有某个有效补全,其下一位必为 。当长度达到 时,唯一可能的后缀为空,于是不变式表明 。机器先做一次初始查询,之后每个见证位至多再做一次查询。构造每个前缀查询并把它归约为 SAT 只需多项式时间。
输出的是在序 下字典序最小的有效见证:在另一个有效见证与它首次不同的位置上,若存在以 开头的有效补全,算法就不可能选择 。字典序最小这一性质是不变式的有用推论,而不是额外的预言机假设。
证明透视
搜索每一位背后的不变式
对 的查询回答“否”之所以有用,只是因为当前前缀 已知存在补全。没有这一不变式,在 0 分支失败之后选择 可能会走向另一个不可能的前缀。初始的存在性查询建立了该不变式,之后的每次查询都保持它。两个分支的角色也不同:“是”不需要再检查,因为它承诺的补全本来就延伸 ;“否”要通过不变式才转化为关于 的信息。最后,机器询问的是 而不是 ,因为 的判定预言机不一定能回答关于部分固定见证的问题。
例题详解
例题 2.4.4
(恢复一个满足赋值)
设 ,变量次序取 。初始查询确认 可满足。固定 后仍有满足的补全,因此选择 0。在该前缀之下,固定 是不可满足的,因此选择 1。输出 满足 ,并且是字典序最小的;另一个满足赋值是 。
概念视角组合
把搜索看成沿二叉树向下走
把长度为 的字符串排成二叉树的叶,其中结点 的两个子结点是 与 。当 ,即它下面的叶中有某个合法见证时,标记结点 。搜索从根出发,根由最初的查询检验;若 被标记就走向 ,否则走向 。它在最左的被标记叶结束,那就是字典序最小的合法见证。
例题 2.4.5
(一个非 SAT 的关系)
设 检查比特串 是否编码了图 中恰好含 个顶点的独立集,其中 包含在输入里,并约定了一种多项式长度的编码。前缀问题问的是:一个部分编码能否补全为这样的集合。它属于 NP,因为剩余的位构成证书的其余部分。SAT 预言机在多项式时间归约之后可以判定每个前缀问题,所以同一搜索过程在这样的集合存在时就能构造出一个。它不需要枚举所有顶点子集。
下面的例子说明,若不先建立不变式,会出现什么问题。
反例模式
跳过初始存在性查询
断言:对前缀 的回答为“否”之后,选择比特 永远正确。取 ,只有一个变量 。两个取值都失败:,。一个跳过初始存在性检查的过程,测试 得到“否”后便自动输出 ,而它并不满足 。断言不成立,因为空前缀本来就没有补全。修正:先查询 。这里答案为“否”,机器报告失败,这才是正确的。
的一个推论
定理 2.4.6
(判定与多项式见证搜索)
若 ,则每个多项式平衡的 NP 关系都有确定性多项式时间的搜索过程,且仅当不存在见证时才报告失败。反之,若每个这样的关系都有确定性多项式时间过程,能在见证存在时输出有效见证(在否例上输出可以是任意的),则 。
证明
(替换预言机;以见证搜索判定 NP)
对于第一个方向,,所以假设给出了每个前缀问题的确定性多项式时间算法。把前一个证明中的预言机调用替换为该算法。调用次数为多项式个,因此完整的搜索仍然是多项式时间。
对于逆向,任取语言 及其多项式平衡的验证者 。运行假设的搜索过程,然后检查返回字符串的长度并计算 。当且仅当检查通过时接受。在是例上,该过程给出有效见证;在否例上,无论该过程返回什么,没有任何字符串能通过验证者。由此得到的确定性多项式时间判定器表明 。由于 ,等式成立。
逆向需要的是一个统一的多项式时间搜索过程,它在每个输入(包括否例)上都停机。若某方法在没有见证时可能永不停止,就得不到所述的多项式时间判定器。
NP 条件与 coNP 条件的结合
定义 2.4.7
(类 DP)
DP 中的语言要求某个 NP 条件成立,同时另一个(可能不同的)NP 条件不成立。
这里的字母是复杂度类的名称,并不表示动态规划。对 NP 取 为空语言,对 coNP 取 为全集语言,即知 NP 与 coNP 都包含于 DP。仅凭这些包含关系,并不能说明任何一个包含是严格的。
定理 2.4.8
(SAT–UNSAT 是 DP 完全的)
由公式对 组成的语言(要求 可满足而 不可满足)在确定性多项式时间多一归约下是 DP 完全的。
证明
(配对两个 NP 归约)
属于 DP 可直接由定义得到:第一个分量属于 SAT,第二个分量不属于 SAT。关于困难性,设 ,其中 。利用 SAT 的完全性,在多项式时间内计算出公式 与 ,使得 当且仅当 可满足,且 当且仅当 可满足。单个映射 满足
两个归约都是确定性的多项式时间归约,所以它们的配对是一个有效的多一归约。无效的编码可以映射到固定的否例;这不会改变完全性。
例题 2.4.9
(两个公式,两种不同的角色)
取 与 。前者可满足,后者不可满足,所以 属于 SAT–UNSAT。把它们交换后得到的是否例:新的第一个公式没有见证。仅仅给出第一个公式的一个赋值,并不能证明第二个公式不可满足。
恰有一个满足赋值
定义 2.4.10
(EXACT-ONE-SAT)
EXACT-ONE-SAT 是由在固定的明确变量列表上恰有一个满足赋值的公式组成的语言。
它属于 DP。“至少一个”这一条件就是 SAT。“至少两个”这一条件也属于 NP:证书由两个赋值组成,二者都满足该公式,并且在所列变量上至少有一处不同。因此
两个检验都可以通过 SAT 查询实现:第二个检验使用变量的两份副本、公式的两份副本,以及一个多项式规模的约束,要求两个赋值不同。因此 EXACT-ONE-SAT 也属于 。
这是一个全语言:具有零个、一个或多于一个满足赋值的公式,其是/否答案都有明确规定。而在“输入保证至多有一个解”的承诺问题中,正确性的要求有所不同。我们不能由 EXACT-ONE-SAT 属于 DP 就推出它是确定性 DP 完全的,也不声称已知它有多项式时间算法。
例题 2.4.11
(零个、一个和两个赋值)
在只列出一个变量 的情形下,公式 有零个满足赋值, 恰有一个, 有两个。只有中间那个公式属于 EXACT-ONE-SAT。其见证 证明了“至少一个”这一部分;而证明不存在第二个赋值,则是另一个独立的 coNP 一侧的任务。
常见错误
常见错误
(判定预言机不是前缀预言机)
针对原始是/否语言 的判定预言机,并不自动成为任意见证关系的前缀预言机。使一般搜索证明成立的,是 的统一 NP 归约。
常见错误
(一个满足赋值不能证明唯一性)
单个有效赋值只证明 EXACT-ONE-SAT 中“至少一个”的一侧,不能排除另一个不同的赋值;属于 DP 本身也不能证明 DP 完全性。
常见错误
(可能在否例上循环的搜索)
允许在否例上永不停机的搜索方法,不是等价定理中所说的确定性多项式时间算法,也无法由它得到 的判定器。
总结
多项式长度的见证可以通过依次询问各个前缀是否有补全而恢复出来。若 P 等于 NP,这些前缀问题无需预言机即可判定;反之,统一的多项式时间见证搜索会判定每一个 NP 语言。类 DP 则把一个 NP 条件与另一个 NP 条件的补的合取明确表达出来。
练习
快速检查
(为什么 属于 NP?)
说明证书是什么,以及验证者检查什么。
解答 · 答案
长度为 的后缀是多项式规模的证书。验证者检查前缀长度并计算 。
快速检查
(当对前缀 的查询失败后,选择比特 1 的依据是什么不变式?)
回想查询之前对 已知什么。
解答 · 答案
当前前缀 已知存在某个有效补全。若没有补全以 0 开头,则至少有一个以 1 开头。
快速检查
(一般搜索算法至多使用多少次 SAT 预言机查询?)
把初始查询与逐位查询分开数。
解答 · 答案
至多 次:一次存在性查询,加上每个见证位各一次查询。
快速检查
(对 ,求字典序最小的满足赋值。)
按 的次序检查赋值。
解答 · 答案
取 ,按 的次序检查赋值; 不满足,第一个满足的赋值是 。
快速检查
(在逆向的证明中,为什么否例上任意的输出仍然会被正确拒绝?)
考虑否例上是否有任何字符串是有效见证。
解答 · 答案
在否例上没有任何字符串是有效见证,所以确定性的长度检查与验证者检查会拒绝搜索过程输出的任何内容。
快速检查
(证明每个 NP 语言都属于 DP。)
把 写成一个语言与另一个语言的补的交集。
解答 · 答案
对 ,写 ,而 。
快速检查
(一个满足赋值本身是否构成“公式恰有一个满足赋值”的证书?)
考虑是否排除了第二个赋值。
解答 · 答案
不是。它证明至少存在一个赋值,但不能排除另一个不同的赋值。
快速检查
(EXACT-ONE-SAT 属于 DP,是否就证明它是 DP 完全的?)
回想完全性的两个部分。
解答 · 答案
不是。完全性还需要在指定归约下证明困难性,而这里只确立了属于 DP。另外,全语言 EXACT-ONE-SAT 对每个编码的公式都规定了答案,而承诺问题的算法只需在满足其承诺的输入上正确。