判定问题询问见证是否存在;计数问题询问见证有多少个。另一种观点的转变,是用一族布尔(Boolean)电路(每个输入长度对应一个电路)取代适用于所有输入长度的单一算法。基本模型的这两种扩展揭示了不同的困难来源。计数衡量解空间的大小,因此其输出所含的信息多于仅记录解空间是否非空的那一个比特。相比之下,非一致电路放宽了“单一有限描述须处理所有输入长度”的要求,而这一放宽以一种在一致图灵(Turing)机模型中没有类比的方式改变了“高效”的含义。本单元仔细展开这两种想法,准确说明使用了哪些假设,并区分此处所证明的内容与作为背景引用的内容。
为什么要计数,为什么要使用电路?
考虑一个由调度或配置问题产生的布尔公式。一个回答“是否存在有效调度方案?”的求解器只给出一个比特的信息。在应用中,人们往往想要更多:有效调度方案共有多少个,所有赋值中有效者占多大比例,或者随机赋值成功的可能性有多大。这些都是计数问题。它们在数学上也很自然,因为非确定型机器的接受路径数是输入的一个定义明确的函数,并且可以用研究语言时所用的同一类基于归约的方法来研究这一函数。
电路处理的是另一个问题。图灵机是一个必须对所有长度的输入都有效的单一有限对象。电路则只是针对某一个长度的有限对象。如果我们问在 个比特上计算一个函数需要多少个门,就得到一种可以不涉及任何机器而加以研究的组合度量。代价是,电路序列不必由任何规则生成。准确理解舍弃这一规则所得与所失,是本单元的第二个主题。
这两个主题在一个共同点上交汇。在这两种情形中,语言 的判定问题都被一个更丰富的对象取代:前者是从字符串到数的函数,后者是有限对象的序列。在这两种情形中,与熟悉的类 进行比较时,都需要仔细说明究竟度量的是什么。
计数见证
定义 5.1.1
(类 #P)
若存在一台非确定型多项式时间图灵机,使得 等于该机器在输入 上的接受计算路径数,则称函数 属于 。等价地,借助多项式时间验证者和固定的多项式见证长度,它对接受的见证进行计数。固定长度的约定保证每个见证恰好对应一条路径。
这两种描述的等价性依赖于一个记账方面的要点。在验证者的表述中,存在一个多项式时间谓词 和一个多项式 ,使得
由于每个见证的长度都恰为 ,不同的见证就是不同的二进制串,而猜测 然后运行 的非确定型机器对每个见证恰有一条路径。若见证的长度可变,则一个字符串可能是另一个字符串的前缀,见证与路径之间的对应就需要另行论证。还请注意 ,所以 的值只有多项式个比特;这就是精确计数函数被写成具有多项式个输出比特的原因。
对于带有指定变量列表的布尔公式 , 对该列表上的满足赋值进行计数。列表是重要的:添加一个未使用的变量会使计数加倍,尽管可满足性不变。判定问题 SAT 只询问计数是否为正。因此,多项式时间的精确计数算法将能判定 SAT,但这一观察并不能确立反方向的蕴含。
这种关系可以表述为一个精确的单向比较。若 可在多项式时间内计算,则对于带有变量列表 的输入 ,我们计算 并恰在其非零时接受,这便判定了 SAT。这个论证中没有任何东西可以逆向进行:一个仅报告是否存在满足赋值的预言机,并不显然地揭示存在多少个满足赋值。下面的计数恒等式则说明了见证的数目是如何组合的。
一个例子
例题 5.1.2
(对赋值计数)
对于指定变量 上的 ,两个子句合起来迫使 ,而 任意。因此 。在变量列表 上,同一表达式的计数为 ,因为未使用的 的任一取值都可扩展每个满足赋值。
这个例子背后的规律是一般性的。若 在 个变量的列表上有 个满足赋值,并且我们再附加 个不出现在 中的变量,则每个满足赋值有 种扩展方式,所以新的计数为 。反过来,在 个变量上计数为 的公式,其在所有赋值中的密度为 ,而附加未使用的变量并不改变这一密度。因此,密度是在变量列表的选择下保持不变的量,而原始计数则不是。
另外两个计数计算
例题 5.1.3
(对带奇偶约束的公式计数)
设 为变量列表 上的公式,其中 为异或。第一个合取项恰在 时成立,第二个恰在 时成立。自由选取 。则 与 被迫确定。因此恰有两个满足赋值,即 与 ,且 。对全部 个赋值逐一枚举检验可证实这一点:赋值 、、、、、 各自违反两个条件之一,只剩下所列出的两个。密度为 。
例题 5.1.4
(按情形计数与补集)
设 为变量列表 上的公式。满足赋值必须使三个变量中至少两个为真,因为若至多一个变量为真,则不含该变量的那个子句(或者当没有变量为真时,任一子句)会不成立。反之,若至少两个变量为真,则每一对变量中都含有一个真变量,所以三个子句都成立。统计至少有两个真变量的赋值:恰有两个为真给出 个赋值,三个全为真给出 个。因此 。作为用补集的交叉检验,使公式为假的赋值是至多有一个真变量的赋值:,并且 ,符合要求。
这些计算之所以容易,仅仅是因为这些公式很小且结构性很强。对于有数百个变量的一般 CNF 公式,目前尚不知道有一般的多项式时间精确计数方法,这正是 引人关注的部分原因。
变量不相交公式的计数
下列恒等式描述了当公式使用不相交的变量时,计数是如何组合的。
命题 5.1.5
(变量不相交公式的合取与析取的计数)
设 是变量列表 上的布尔公式, 是列表 上的布尔公式,其中 与 不共享任何变量。下面右侧的计数分别使用各自的列表 与 。则在合并列表 上,
此外,在同样的假设下,。
证明
(证明)
合并列表上的赋值是一个二元组 ,其中 为 的赋值, 为 的赋值。由于 只涉及 ,它在 处的真值仅取决于 ;同样, 的真值仅取决于 。令 且 ,于是在各自的列表上 且 。
对于合取, 满足 当且仅当 且 ,所以满足集是笛卡儿积(Cartesian product) ,它有 个元素。
对于析取, 满足 当且仅当 或 。满足 的二元组构成的集合是 ,大小为 。满足 的集合是 ,大小为 。它们的交集是 ,大小为 。由容斥原理得 。
证明透视
变量不相交在哪里用到
整个证明依赖一个化归:二元组 满足 当且仅当 ,满足 当且仅当 。这是因为 不含 中的变量, 不含 中的变量;这也是唯一用到该假设的地方。有了这一点,合取的满足集就是乘积集 ,析取的满足集则是两个柱集 与 的并集。并集的大小并不等于两个柱集大小之和,因为它们恰好在 上重叠;容斥原理把这个重叠部分扣除一次。若 与 共用某个变量,“”与“”就不再是对不同坐标的条件,满足集也就不是乘积集,合取的计数便无法从两个单独的计数直接读出。
作为数值检验,取 (于是 ,计数为 )和 (于是 ,计数为 )。析取公式给出 。直接计算,三个变量上的 仅在 且 时为假,这样的赋值有 个,所以它在 个赋值上为真。两种计算一致。
该命题表明,对于变量不相交的公式,计数可以分解为乘积,而判定问题只看每个因子是否非零。它也提醒我们,析取并不具有可加性:析取的计数取决于两边各自的变量数,这是对变量列表依赖性的又一个例子。
电路与非一致观点
布尔电路是由门构成的有限有向无环图,其输入节点携带比特或常量;它的规模是门的个数。若对每个 , 对每个 比特字符串都给出正确的成员资格比特,则称电路族 判定一个语言。类 由具有多项式规模电路族的语言构成。该电路族不必能由 计算出来:这就是非一致性的特征。通过展开一个多项式时间的计算, 中的每个语言都有多项式规模的电路;我们不加证明地使用这一模拟定理。
具体地说, 意味着存在多项式 与电路 ,使得 至多有 个门,并且对每个 , 当且仅当 。量词结构是“存在一个序列”,而不是“存在一个产生序列的算法”。这是与一致定义之间唯一的差别,而下一个结果表明这个差别是实质性的。
命题 5.1.6
(非一致性可以编码不可判定的信息)
中存在一个不可判定的一元语言。
证明
(证明)
的子集有不可数多个,而图灵机只有可数多个,因此可选取一个不可判定的一元语言 。对每个长度 ,令 先检查其 个输入比特是否全为 ,然后输出硬连线的、指示是否 的比特。该电路有 个门。其硬连线比特的选取不必能由 计算出来,并且该电路族在所有二进制串上判定 。因此,仅有多项式电路规模并不蕴含可判定性。
这一构造值得仔细考察。当 时,“所有输入均为 ”的检验是 个输入的合取,需要 个二元 AND 门。硬连线比特 随后或者通过再加一个 AND 门来组合(若 ),或者被常量 输出所取代(若 )。对 ,总数至多为 个门;当 时,使用适当的常量输出。该电路族的规模当然是多项式的。不可判定性完全来自序列 ,而没有任何算法能产生这个序列。
反例与精确假设的作用
三个小的观察说明了为什么前面陈述中的假设不能随意去掉。
第一,没有变量不相交性,分解式不成立。
反例模式
共用变量时分解式不成立
假设有人声称对所有公式都有 。取 与 ,位于单变量列表 上。则 (只有 ),(只有 ),乘积为 。但 没有任何满足赋值,其计数为 。修补办法就是命题的假设: 与 必须使用不相交的变量列表,这样满足的二元组才是“独立地选一个满足 的 与一个满足 的 ”。
共享变量使各因子相互耦合,因此不能假定这两个选择相互独立。
第二,计数取决于所声明的变量列表。公式 在列表 上的计数为 ,但在列表 上的计数为 。任何省略列表的关于 的陈述都是有歧义的。
第三,如硬连线的一元语言所示,没有一致性的多项式电路规模本身并不保证存在算法。相比之下,一致族是指这样的族:一台多项式时间机器在输入 上输出 的描述。对于这样的族,该语言属于 ,因为只需构造 并对其求值。这就是从多项式时间一致族到 的包含关系。其逆,即通过展开多项式时间机器来构造多项式时间一致族,是一个标准的模拟结果,此处不加证明地使用。
此处引用而未证明的内容
矩阵的积和式以及“计算它是 完全的”这一定理是进一步的核心例子;Valiant 定理在此不予证明。本单元也不证明 Toda 定理或 Karp–Lipton 定理。这些结果需要精确的归约、预言机约定和额外的工具,才能被负责任地使用。未经证明的依赖包括:为验证者等价性所做的非确定型机器的规范化,以及用一致的多项式规模电路对多项式时间计算的模拟;其余一切,包括乘法性命题及不可判定性的例子,都已从定义出发得到证明。
常见错误
(电路并不自动就是一致算法)
每个电路规模上的多项式界,并不提供从 构造该电路的多项式时间过程。一致性是一个额外的要求。硬连线的一元例子使这一区别具体化。
常见错误
(在不给出变量列表的情况下读取计数)
引用“ 的满足赋值的个数”而不指明变量列表是不完整的,因为每个未使用的变量都会使计数加倍。只有在共同的列表上,或者在除以 得到密度之后,比较两个公式的计数才有意义。
练习与解答
快速检查
( 在变量列表 上有多少个满足赋值?)
数一数不满足的赋值。
解答 · 答案
三个:除 之外的所有赋值都满足该公式。
快速检查
(为什么多项式规模的电路族不一定能由图灵机判定一个语言?)
想想定义对从 到 的映射有什么要求。
解答 · 答案
定义对从 到 的映射没有任何可计算性要求。该电路族可以硬连线一个不可判定的比特序列,如一元例子所示。
快速检查
(利用乘法性命题,计算 在列表 上的 。)
先检查两个合取项是否使用不相交的变量。
解答 · 答案
公式 (变量 )与 (变量 )变量不相交。 的计数为 , 的计数为 ,所以乘积为 。直接计算: 被迫确定,且 ,给出 个赋值。
快速检查
(一个公式在 个变量的列表上有 个满足赋值。附加 个未使用的变量之后,其计数和密度分别是多少?)
每个满足赋值有 种扩展方式。
解答 · 答案
新的计数在 个变量上为 。之前的密度为 ,之后为 ,不变。
快速检查
(证明:若 ,则其补集也属于 。)
把每个电路稍作修改。
解答 · 答案
给定 的电路 ,其规模至多为 ,通过在 的输出之后添加一个 NOT 门,形成 。它至多有 个门,仍是多项式的,并且对长度为 的 , 恰当 。请注意,这里不需要也没有用到一致性。