多项式时间归约

所有内容:NP与计算的难解性

1 多项式时间归约

1.1 归约的概念

在研究不同问题的难度时,希望表达“问题X至少像问题Y一样的难”,这就是归约。

1.2 多项式时间归约

在计算模型中,假设问题X可以在多项式时间内求解。如果有一个解决问题X的“黑盒子”,假设通过多项式次调用解问题X的黑盒子,可以解决问题Y,则说明问题X有足够的能力解决问题Y,称作“Y多项式时间可以归约到X”。
记作:Y \leq_p X,读作“Y多项式时间可以归约到X”或者“X至少像Y一样难。”
则,我们可以得到以下定理:
定理1.假设Y \leq_p X,如果可以在多项式时间内求解,则也可以在多项式时间内求解。
定理2.设Y \leq_p X,如果不能在多项式时间内解决,则X也不能在多项式时间内解决。

1.3 独立集与顶点覆盖之间的归约

【独立集问题(Independent set)】
一个独立集(也称为稳定集)是一个图中一些两两不相邻的顶点所形成的集合。即顶点集合的任意两个点之间没有边。如图1,红色的点集合都是独立集,任意两个红色的顶点没有边。
在这里插入图片描述
图1 独立集(红色)
【顶点覆盖问题】
图的顶点覆盖也是一个点的集合。图中每一条边都至少有一个顶点在点集合中。如图2,黑色的点集合都是顶点覆盖集合,图的每一条边都至少有一个顶点在点集合中。
在这里插入图片描述
图2 顶点覆盖集(黑色)
【独立集与顶点覆盖之间的归约】
独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗?
顶点覆盖问题:给定图G和数k,G是否包含大小为k的顶点覆盖?
证明两个问题的难度是等价的。
定理3:设G=(V,E)是一个图,S\subseteq V,则S是一个独立集当且仅当它的补图V-S是一个顶点覆盖。
证明:
设S是一个独立集,考虑任意的一条边,因为S是独立集,则u和v不可能都在S中,因此u和v必有一个在V-S中。则每一条至少有一个端点在V-S中,即V-S是一个点覆盖集合。
反过来,假设V-S是一个顶点覆盖。考虑S中的任意两个顶点u和v,如果它们之间有一条边e,则e的两个端点都不在V-S中,则与假设V-S是一个顶点覆盖矛盾。因此,S中的任何两个顶点之间都没有边,则S是一个独立集。
【独立集\leq_p顶点覆盖】
证明:如果有一个解顶点覆盖的黑盒子,则通过问黑盒子G是否有大小至多为n-k的顶点覆盖,可以确定G是否有大小至少为k的独立集。
【顶点覆盖\leq_p独立集】
证明:如果有一个解独立集的黑盒子,则通过问黑盒子G是否有大小至多为n-k的独立集,就能够确定G是否有大小至少为k的独立集。

1.4 顶点覆盖到集合覆盖的归约

对于顶点覆盖问题,可以看做是“覆盖问题”,目标是用尽可能少的顶点“覆盖”图中所有的边。
【集合覆盖问题】
集合覆盖问题可以描述为:
给定 n 个元素的集合U,U 的子集S_1,…,S_m 以及数 k, 问在这些子集中有一组子集,它的并等于整个 U 且至多含有 k 个子集?
如图3为一个集合覆盖问题的实例。
在这里插入图片描述
图3 集合覆盖问题实例
在图3中,有3个子集(即数k为3){S_3,S_4,S_5},它的并等于整个 U。
【顶点覆盖\leq_p集合覆盖】
顶点覆盖问题可以归约到集合覆盖问题。
即:如果有一个解集合覆盖的黑盒子,通过输入顶点覆盖的一个实例,调用这个黑盒子,能够解决顶点覆盖问题。
可以使用这样的构造方法:对于每一个顶点i \in V,设集合S_i \subseteq UG 中所有与顶点 i 相连的边。则根据此方法,对每一个顶点构建集合。
U 能够被 S_1,S_2,S_3,…,S_n 中至多 k 个集合覆盖当且仅当 G 有大小至多为 k 的顶点覆盖。
因为如果 S_{i_1},S_{i_2},S_{i_3},…,S_{i_ll \leq k 个覆盖 U 的集合,那么 G 中的每一条边都可以关联到顶点 i_1,i_2,i_3,…,i_l 中的一个,所以 {i_1,i_2,i_3,…,i_l} 是 G 中大小为 l \leq k 的顶点覆盖。
因此,给定顶点覆盖的实例,利用上述构造方法构造集合覆盖的实例,并且将它输入黑盒子,回答yes当且仅当黑盒子回答yes。

1.5 独立集到集合包装的归约

对于独立集问题,可以看做是“包装问题”,它的目的是装入更多的顶点。
【集合包装问题】
集合包装问题可以描述为:
给定 n 个元素的集合 U , U 的子集 S_1,S_2,…,S_m 以及数 k , 问在这些子集中至少含有 k 个集合两两不相交?
【独立集 \leq_p 集合包装】
集合覆盖是顶点覆盖的自然推广,集合包装是独立集的自然推广。使用同样的构造方法和相似的证明方法,能够证明独立集问题可以归约到集合包装问题。

,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥♥,.,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥
广告时间:
本宝宝开通了一个公众号,记录日常的深度学习和强化学习笔记。希望大家可以共同进步,嘻嘻嘻!求关注,爱你呦!
在这里插入图片描述

0

Leave a Reply

Your email address will not be published.