某些算法问题中,检查给定的解似乎比找出解容易。给定顶点列表,检查每对顶点是否相邻并不困难;要找出大的相邻顶点集合,却可能需要检查过程无须作的选择。复杂度理论精确描述这个差别;归约让我们保留问题之间的逻辑关系,传递求解方法与困难性。
动机
若有人提出适用于任意图的快速大团算法,可把另一搜索问题高效地翻译成图,使原解对应于团。图算法便能经这个翻译求解原问题。这个翻译称为归约,其方向决定算法能传到哪一方。
我们先把问题写成是非判定。CLIQUE 询问图是否含有大小至少为指定值的团;归约只需保留这个真值。优化与搜索问题还需额外论证:判定答案不会自动给出实际的团。
构造从短子句的合取公式开始。每个子句至少要有一个真文字。我们为每次文字出现建立顶点,并连接来自不同子句且相容的选择。触及每个子句的团,便表示一组全局一致的满足选择。必须证明双向对应;只从满足赋值建团,还不能排除不可满足公式产生团的错误肯定结果。
定义
语言 是答案为“是”的有限二进制字符串集合,用来表示判定问题。固定图、公式与整数的编码,拒绝格式错误者。输入规模 指编码长度,而非所含最大数。在标准离散比特模型上,类 由可用确定性算法在关于 的多项式时间内判定的语言构成。
若存在确定性验证器 和多项式界 ,使得
则称语言属于 ,其中对于长度不超过该界的见证,验证所需时间是关于 的多项式。字符串 称为证书或见证。这个等价式要求每个是实例都有见证,并且禁止任何接受性见证对应于否实例。如果检验一个见证需要指数时间,那么仅有短见证是不够的。如果允许见证任意长,而只要求关于该见证的多项式时间,也不满足上述类的定义。
多项式时间多一归约 是一个可在多项式时间内计算的全函数 ,使得对每个输入串 ,都有 当且仅当 。它翻译输入,并保持其是或否的答案。若 NP 中的每个语言都可归约到语言 ,则称 是 NP 难的。若 既是 NP 难的又属于 NP,则称它是 NP 完全的。仅有难度并不能确立属于 NP。
在有限简单无向图 中,团是这样的顶点子集:其中任意两个不同顶点之间都有边。独立集是其任意两个不同成员之间都没有边的顶点子集。顶点覆盖是与每条边都相交的顶点子集。CLIQUE 和 INDEPENDENT SET 询问是否存在相应类型、大小至少为 的集合;VERTEX COVER 则询问是否存在大小至多为界 的集合。我们使用非负整数阈值,平凡的越界情形可以直接判定。
图以显式顶点及边列表,或邻接矩阵编码;孤立顶点也占用空间。因此顶点数由输入长度的多项式界定。只用二进制顶点数隐式表示指数多个孤立顶点,属于另一输入模型,不适用于下文归约。
布尔(Boole)文字是一个变量或其否定。子句是若干文字的析取,合取范式(CNF)是若干子句的合取。这里的 3SAT 指子句至多含三个文字的 CNF 公式的可满足性。子句可以只含一个或两个文字;如果希望采用另一种约定,可以通过重复某个文字把它们补足为恰好三个。含有空子句的公式不可满足,而不含任何子句的合取则为真。
定理/命题
定理 13.1.1
(归约传递算法并且可以复合)
若 且 ,则 。多项式时间多一归约是传递的。因此,若 是 NP 难的且 ,则 是 NP 难的。若此外 ,则 是 NP 完全的。
定理 13.1.2
(三个等价的图证书)
设 有 个顶点, 为它的简单补图:其中两个不同顶点相邻,当且仅当它们在 中不相邻。对于 ,
这些等价关系给出多项式时间归约,并且这三个判定问题都属于 NP。
定理 13.1.3
(选取相容的文字产生团归约)
给定一个含有 个非空子句的 3CNF 公式,为每个文字出现创建一个顶点。当且仅当两个顶点属于不同的子句,并且它们的文字不是某个变量与其否定时,在它们之间连边。该公式可满足,当且仅当所得的图含有大小至少为 的团。该构造至多有 个顶点,其编码长度和构造时间都是多项式的。
证明思路或证明
证明
(归约可复合并传递算法)
要借助 的判定器来判定 ,先计算 ,再在其上运行该判定器。多项式时间的翻译至多只能输出多项式个比特,因此 是关于 的多项式。于是,关于 的多项式运行时间,仍然是关于 的多项式。两个翻译的复合保持答案的等价性以及同样的长度界,由此证明传递性。NP 难度的蕴含由以下复合得到:把 NP 中任一语言归约到 的归约,与给定的从 到 的归约相复合。
证明
(三个图等价关系及其验证器)
对于图的等价关系,子集内的每一对不同顶点在 中都由边连接,当且仅当其中每一对顶点在补图中都是非边。此外,对任意图 ,集合 是独立集,当且仅当 是顶点覆盖。事实上,未被覆盖的边的两个端点都在 中,而这样的边恰恰就是独立性的失败。对顶点子集取补集,把大小 变成 ,从而把下界阈值 变成上界阈值 。在邻接矩阵表示下,构造图的补图需要 次顶点对检查。
要验证团,检查给定的列表是否含有至少 个互不相同的合法顶点,并检查每一对顶点。独立集的验证器检查这些顶点对之间没有边;顶点覆盖的验证器扫描所有边,检查每条边都有一个端点在列表中,并检查列表大小至多为给定的界。顶点列表的长度是多项式的,每项检查也是多项式的。属于 NP 的证明独立于难度的证明。
证明
(子句到团的归约)
现在取公式的一个满足赋值。在每个子句中选取一个为真的文字出现。所选顶点属于不同的子句,并且没有两个所选文字互补,因为一个赋值不可能使两者同时为真。所以所有顶点对都是边,这 个顶点构成一个团。
反之,团中没有两个顶点来自同一子句,因为该构造在子句内部不放置任何边。团至多有 个顶点。因此,大小至少为 的团恰好在每个子句中含有一个文字出现。所选的出现中没有互补的文字。把每个被选中的正变量设为真,把每个被选中的负变量设为假;两两一致性保证这些指令是相容的,即使同一个变量被多次选中也是如此。对从未被选中的变量任意赋值。每个子句都有一个被选中的真文字,因此整个公式被满足。
文字出现至多有 个,所以检查每一对是多项式的。文字的变量名同样占用比特;构造时间包括比较这些名字,并且仍是关于整个公式编码长度的多项式。含有空子句的公式可以直接映射到一个固定的否 CLIQUE 实例,空合取则映射到一个固定的是实例。格式错误的源字符串同样映射到一个固定的否实例。这使归约成为全函数,而不会留下未定义的特殊编码。
证明透视
缺失的边与存在的边各有其作用
省略子句内部的边,迫使大团触及互不相同的子句。省略互补文字之间的边,使所选的指令保持一致。阈值则迫使每个子句都有代表。这是三项相互独立的义务;只满足其中两项的图编码,可能接受本应被拒绝的公式。
证明
(以至多三个文字的子句取代 SAT)
为完整起见,说明为什么可以用 3SAT 代替 SAT。用二元 AND、OR 门和一元 NOT 门表示一个布尔公式,并为每个内部门的值引入一个新变量。对于 AND 门 ,施加子句 、 和 。对于 OR 门,使用 、 和 。对于 NOT 门 ,使用 和 。最后用一个单位子句断言输出变量为真。
各组子句恰好强制对应的门真值表。原满足赋值按实际门值扩展后满足全部子句;反之,子句的满足赋值沿门序必须符合每个门并令输出为真。新增变量与子句数对公式树大小为线性,故转换在多项式时间内保留可满足性,且各子句至多三个文字。结合所引 Cook–Levin 定理,3SAT 是 NP 完全的;图归约再把困难性传至 CLIQUE、INDEPENDENT SET 和 VERTEX COVER。
例题详解
例题 13.1.4
(从相容的选择中读出赋值)
取 。它的三个子句组含有六个文字出现顶点。在第一个子句中选 ,在第二个中选 ,在第三个中选 。它们两两不互补,因而构成一个三元团。它们的指令给出 为真、 为真、 为假,满足每个子句。若在前两个子句中选取 和 ,则无论第三个如何选择都会失败,因为对应的顶点之间没有边。
例题 13.1.5
(对子集取补时阈值会改变)
设 是有四个顶点、边为 的路。集合 是独立集,其补集 是顶点覆盖。在 中,顶点对 是一个团。因此,CLIQUE 实例 映射到独立集实例 ,再映射到顶点覆盖实例 。图的补改变邻接关系;子集的补改变大小阈值。它们是不同的运算,尽管这个例子同时用到了两者。
例题 13.1.6
(为什么数值参数可能误导对运行时间的论断)
对于非负整数元素和目标值 的 SUBSET SUM,通常的动态规划记录从零到 的哪些和可以取到,可以使用 次表更新。若 ,则其二进制编码只需 位,而表却有 项。该算法关于数值 是多项式的,但并不因此就关于二进制输入长度是多项式的。这样的界称为伪多项式的。这一观察解释的是代价模型,并不是 SUBSET SUM 的 NP 难度的证明。
常见错误
反例模式
子句内部的边会接受不可满足的公式
一个诱人的变体是把同一子句内的顶点也连起来,理由是多加边只会使大团更容易找到。把它用在不可满足的公式 ()上:第一个子句中 的两个出现就相邻,构成大小为 的团,但没有任何赋值满足该公式。原构造不在子句内部连边,正是为了使大小为 的团必须恰好使用每个子句一次。
常见错误
(归约方向弄反)
要证明新问题 是困难的,应当把一个已知的困难问题归约到 。从 到已知困难问题 的归约 ,只在 可解时才提供解 的方法。容易的语言也可以归约到许多困难的语言。箭头本身表达的是一种算法上的蕴含,而不是对称的比较。
常见错误
(误解 NP 这个名称)
NP 不表示“非多项式”。P 中的问题都在 NP 中:验证器忽略空证书并运行判定器即可。因此 NP 完全性并没有证明多项式算法不存在。若某个 NP 完全语言在 P 中,归约定理就会使所有 NP 语言属于 P;是否如此,正是 P 对 NP 问题。NP 的“非确定性”也不同于随机化:这里验证器是确定性的,由存在的见证提供成功的选择;随机抽样找不到见证,并不能证明它不存在。
常见错误
(在归约内部先解决源问题)
归约应当在不先解决源问题的前提下变换输入数据。“若公式可满足则输出一个是图,否则输出一个否图”在数学描述上保持了答案,但并没有建立任何多项式时间的构造。相容出现的构造之所以成功,是因为它直接由局部语法构建图。
总结
NP 描述多项式长度、可高效验证的证书。多一归约须在多项式时间内翻译每个输入,同时保留是与否的答案。子句文字出现把满足选择编码为团;图补及子集补再连到独立集与顶点覆盖。NP 成员资格、困难性与引用的基础定理,各有独立的证明义务。
练习
快速检查
(说明哪个归约方向能让 VERTEX COVER 的多项式时间算法解决 3SAT,并指出两次图归约之后的阈值。)
解答 · 答案
使用 。对于有 个非空子句的公式,其出现图 有 个顶点,团阈值为 。在补图中,独立集阈值为 ,最终的顶点覆盖阈值为 。空子句和空合取这两种例外输入,按构造中所述被直接判定并映射到固定的实例。
快速检查
(在子句到团的构造中,假设在不同子句里带互补文字的两个顶点之间也加上边。给出一个不可满足的公式,使其产生错误的肯定结果。)
解答 · 答案
公式 不可满足,且 。加上多余的边后,第一个子句中的顶点 与第二个子句中的顶点 构成大小为 的团,图因而被错误地接受。缺少互补文字之间的边,才使所选的文字相互一致。
快速检查
(给出判定问题“这个非空有限无向图是否有一条恰好经过每个顶点一次的简单路径?”的多项式证书和验证器。)
解答 · 答案
给出所有顶点的一个有序列表。检查其长度等于顶点数,每个合法顶点恰好出现一次,并且列表中每一对前后相接的顶点之间都有边。在标准的顶点标号编码下,该列表有 位,检查需要多项式时间。单顶点图有一条仅包含该顶点的路径。这证明该问题属于 NP;并不建立该路径问题的 NP 难度。
快速检查
(为什么 NP 完全问题的某个固定的容易实例并不与 NP 难度矛盾?请区分实例与语言。)
解答 · 答案
NP 困难性针对整个任意编码输入族及其多项式算法。固定图的答案可存为常数,某些特殊图类也可有快速算法;两者都未提供判定所有无限制实例的算法。
练习 13.1.7
(证明:若 且 ,则 。)
核心证明
解答(3)
- 1
为 建立验证器
对输入 与见证 ,先用该归约计算 ,再在 上运行 的验证器 。
- 2
界定见证长度与运行时间
关键一步
归约是多项式时间的,所以 受 的某个多项式所限。把它代入 的见证长度界与验证时间,就得到关于 的多项式;再加上计算 的时间,总时间仍是多项式。
依据: 输出长度的界是多项式时间归约本身所提供的。
- 3
得出属于 NP
∎当且仅当 ,当且仅当 在 上接受某个短见证。因此新的验证器恰好对 的成员接受某个见证,即 。