动机
判定问题的归约只需保持解是否存在。计数归约则必须更加谨慎:引入辅助选择可能使一个解变成多个解,从而改变答案。简约(parsimonious)归约保持精确的计数。我们将构造一个从布尔(Boolean)电路到三文字子句的简约归约,并借此看清计数与普通可满足性有何不同。随后我们研究积和式(permanent),其中对置换求和即可数出二部图中的完美匹配。
对于带有已声明的 个变量列表的布尔公式, 是使该公式为真的、对该列表的赋值个数。未被使用的已声明变量仍然贡献选择数。在本单元中,3-CNF 公式的每个子句至多含三个文字;若要求每个子句恰有三个文字出现,则可通过重复某个文字来补足任何非空的较短子句,而不改变满足赋值的集合。归约所引入的变量被包含在输出的变量列表中,因此除非子句唯一地强制其取值,否则它们会对计数产生贡献。
从计数函数 到 的简约归约是一个多项式时间可计算的映射 ,对每个输入都满足 。这比仅保持取值是否为零要强。其他计数归约(包括预言机归约)有不同的定义;完全性结果必须说明它使用的是哪一种。例如,添加一个无约束布尔变量的变换会把计数 变为 。将返回的计数除以二即可恢复 ,但这个原始映射并不是简约的。当某个构件对不同的输入赋值产生不同数量的扩张时,这一区别就更为重要:单一固定的除数因子可能失效。
为什么判定构件可能改变计数
反例模式
辅助变量可以改变计数
假设有人声称,任何保持可满足性的变换也保持满足赋值的个数。取公式 ,其声明变量列表为 ,它恰有一个满足赋值。在变量列表 上的公式 恰在 可满足时可满足,但它有两个满足赋值: 配 ,以及 配 。新增的变量没有约束。该变换保持了解的存在性,但不是简约的;修补办法是要求每个输入解恰有一个输出扩张。
常见错误
(等可满足并不意味着解的个数相等)
若证明了每个输入解至少有一个输出扩张,且每个输出解都投影为某个输入解,则只确立了可满足性等价。要保持精确计数,还需要每个输入解恰有一个输出扩张,或者存在某个显式的保计数双射。仅仅引入辅助变量并检验“是/否”方向,并不能确立这一性质。
编码单个布尔门
假设电路具有由 AND、OR、NOT 和常量门构成的拓扑序,每个 AND/OR 门有两个输入,每个 NOT 门有一个输入。为每个门的输出引入一个新变量。对于门 ,施加
若 ,前两个子句迫使 。若 ,第三个子句迫使 。因此这些子句恰在 时成立,并且一旦固定 ,允许的 是唯一的。
OR 门与 NOT 门可作同样的分析。对 与 ,分别施加
对 OR 门,前两个子句使 或 时 ,第三个子句使 时 成立;对 NOT 门, 迫使 , 迫使 。在每种情形下,这些子句恰在 等于门运算作用于其输入的结果时成立,而且 由输入唯一确定。常量一门配以单位子句 ,常量零门配以单位子句 ;两种情形下其输出都被唯一地强制确定。门之间可以共享前驱;每个门仍然拥有自己的输出变量。下面的计数论证则补充了输入赋值与辅助变量赋值之间的全局双射。
例题 5.3.1
(双向检验一个 AND 门)
若 ,子句 迫使 ,而当 时三个子句全部成立。若 ,子句 迫使 ,这同样满足其余子句。其余两个输入对的情形类似。对每个固定的输入对,恰有一个合法的 ,且等于 。
定理 5.3.2
(从电路到 3-CNF 的简约归约)
存在一个多项式时间映射,把带有已声明输入变量列表的布尔电路 映为 3-CNF 公式 ,使得 在其所有已声明变量上的满足赋值个数等于 所接受的输入赋值个数。
证明
(证明)
为每个门创建一个新变量,并加入相应的门等价子句。再加入一个单位子句,迫使输出门的变量取一。若输出直接是某个输入,则使用该输入的单位子句。若输出直接是常量,则添加一个新变量 :对常量一,强制 ;对常量零,同时施加 和 。这两种情形分别恰好把每个输入赋值保留一次,以及不保留任何输入赋值。新变量与子句的数目关于电路描述是线性的。若采用此约定,重复某个文字即可把较短的非空子句补足为恰有三个文字出现;这不会引入新变量或新的满足赋值。
固定对已声明输入变量的任一赋值。按拓扑序对电路求值,并给每个新变量赋以其门的实际值。所有门子句均成立。反之,在任一满足赋值中,每个门的子句迫使其新变量等于对前驱取值作用该门运算的结果。沿拓扑序作归纳可知,每个门变量都等于对 求值所得的值。因此固定的输入赋值恰有一个满足所有门子句的扩张。输出子句接受该扩张,当且仅当 输出一。于是,向输入变量的投影是从 的满足赋值到 的接受输入赋值的双射,从而两者计数相等。
证明透视
为何不仅需要扩张存在,还需要它唯一
这个归约需要门变量的两项事实,它们的作用不同。扩张的存在性(按拓扑序对电路求值即得)说明每个被接受的输入都会保留下来;唯一性(因为在前驱固定后,每个门的子句迫使其变量取定值,沿拓扑序归纳即得)说明它恰好保留一次。可满足性等价只需要存在性;简约性则两者都需要。输出门上的单位子句随后从输入中恰好选出那些其唯一扩张的输出为一的输入。若没有这个子句,每个输入赋值仍恰有一个扩张,而公式在 个输入变量上就有 个满足赋值,与电路计算什么无关。
该证明同样处理了未被使用的输入变量:其取值在双射两侧都仍是自由的输入选择。这一构造常被称为门编码,但此处的关键性质是辅助变量取值的唯一性,必须经过验证而不能凭名称推断。
例题 5.3.3
(数一个小的已编码电路)
设 ,并引入一个门变量 。加入三个 OR 等价子句和单位子句 。被接受的输入赋值为 、 和 。对其中每一个,门子句迫使 ;赋值 迫使 ,从而违反单位子句。因此输出公式在 上恰有三个满足赋值,而不是六个。
若从一个 见证验证者出发,则标准的、以多项式规模电路对多项式时间确定性计算作一致模拟,给出一个电路:其输入比特为见证,而 被硬连线为输入。把该模拟与上述定理复合,便得到到 的简约归约。我们在此把图灵(Turing)机到电路的模拟作为明确不加证明的背景定理使用。门编码本身已在上文证明;不应把它误认为是对该模拟的证明。
积和式与完美匹配
对于 矩阵 ,定义其积和式为
这与行列式相似,但不给奇置换附加符号。对于 – 矩阵,把第 行与第 列视为二部图两侧的顶点,当且仅当 时有边 。
命题 5.3.4
(0–1 矩阵的积和式数出完美匹配)
对于 – 矩阵 , 等于其对应二部图中完美匹配的个数。把 映为该积和式的函数属于 。
证明
(证明)
置换 为每一行恰选一列,并且每列恰用一次。乘积 等于一,当且仅当所选的所有对都是边;此时这些对构成一个完美匹配。反之,每个完美匹配在每一行中选取唯一的一列,因而对应唯一的置换。所有其他乘积均为零,故该和数出的是匹配的个数。
为把该计数表示为 的见证函数,用定宽二进制块编码一个由 个列下标构成的建议序列。多项式时间验证者拒绝越界或重复的下标,并检验每一条建议的边都存在。每个完美匹配恰有一个这样的有效序列,而无效的编码都被拒绝。因此被接受的见证串个数就是积和式。 的情形可以对每个下标使用一个比特,有限个例外规模可以显式处理。
例题 5.3.5
(一个 积和式)
对于
考虑第一行所用的列。若它用第 列,则其余的 子矩阵全为一,贡献两个匹配。若它用第 列,则第 行必须用第 列,于是第 行用第 列,贡献一个。第 列对第 行不可用。因此 。该论证数的是匹配,而非带符号的项;行列式可能与之不同。
奇偶性比精确计数更易提取
在域 上,。行列式的展开式为
把各元素及整数行列式模二约化后,每个符号都等于一,故 。在 上做高斯(Gauss)消元法可在多项式时间内计算行列式。因此,用这种方法可以判定二部图中完美匹配的个数是否为奇数,而无需精确计算该个数。
命题 5.3.6
(0–1 矩阵的积和式奇偶性)
对于 – 矩阵 , 的奇偶性可在确定性多项式时间内计算。
证明
(证明)
把 约化为 上的矩阵。在置换展开式中逐项比较,行列式与积和式在该域中一致,因为每个置换的符号都是 。初等行变换只需多项式次域运算即可计算行列式;交换两行会改变通常的符号,而该符号在 中同样是 。所得结果就是积和式模二约化后的值。它等于一,当且仅当整数计数为奇数。
例题 5.3.7
(即使存在匹配,奇偶性也可能为零)
对于全一的 矩阵,每个置换对应一个完美匹配,共有两个。其积和式为 ,故奇偶性为零。其行列式模二也为零,因为它的两行相等。因此偶数的奇偶性并不意味着不存在匹配;它只说明精确计数是偶数。
著名的结论——– 积和式的精确计算在适当的计数归约下是 完全的——即 Valiant 定理。此处不予证明。多项式时间的奇偶性计算并不证明精确的积和式计算是容易的,而仅凭属于 也不能证明其困难性。同样,Toda 定理需要超出本单元各构造的额外预言机与归约工具。
具有多项式时间递推的计数问题
并非每个计数问题都在同样的意义下困难。在有限有向无环图中,从某个顶点到指定目标的有向路径条数可以通过动态规划计算。令 ,对应从 到自身的空路径。按逆拓扑序处理其余顶点,并令
从 出发的每条路径恰以一条出边开始,因此各求和项所数的集合互不相交。没有通向 的路径的顶点得到零。源点处的值即所求计数。
例题 5.3.8
(不逐一列出而数有向路径)
设边为 。从目标开始,得 与 。然后 ,,以及 。三条路径为 、 与 。该递推按首条边对它们分组,并且每条恰好数一次。
对于具有 个顶点的简单无环图,一条路径至多经过每个顶点一次。可能的顶点序列数有一个粗略上界 ,其比特数仅为 ,故递推中所有计数的比特长度都是多项式的。因此,多项式次加法即给出多项式时间的精确算法。无环性假设对这一简单递推是本质的:有向圈可产生无穷多条途径(walk),而即使只数简单路径,递推也必须记住哪些顶点已被使用。这个例子还表明,仅凭属于 并不能说明某个特定的计数是否困难。
练习与解答
快速检查
(为什么添加一个无约束的新布尔变量通常会使满足赋值的计数翻倍?)
想想新变量可取多少个值。
解答 · 答案
每个原有的满足赋值恰以两种方式扩张,即新变量取零或取一。没有新的子句限制它。
快速检查
(若 且 ,满足 AND 门等价子句的 取何值?)
留意含 的子句。
解答 · 答案
子句 迫使 。当 时,三个 AND 等价子句全部成立。
快速检查
(为什么电路到 CNF 的证明对每个输入赋值恰给出一个扩张?)
按拓扑序逐个门考虑。
解答 · 答案
每个门的子句把该门的输出强制为其已确定的前驱的函数。沿拓扑序作归纳,可唯一确定每个辅助变量。
快速检查
(计算 的积和式。)
对 的两个置换求和。
解答 · 答案
共有两个置换,每个都贡献一,所以积和式为 。
快速检查
(若某个 – 矩阵的积和式为奇数,它在 上的行列式是多少?)
比较两个展开式模二的结果。
解答 · 答案
为一:行列式与积和式模二一致。
快速检查
( 上行列式为零,能否证明二部图没有完美匹配?)
试试全一的 矩阵。
解答 · 答案
不能。这只证明匹配的个数是偶数。全一的 矩阵有两个匹配,而其在 上的行列式为零。