大数据

当前位置:首页 > 大数据

《算法导论》第三十四章(续5)

34.5NP完全问题

NP完全问题产生于各种不同领域:布尔逻辑,图论,算法,网络设计,集合与划分,存储与检索,排序与调度,数学程序设计,代数与数论,游戏与难解问题,自动机与语言理论,程序优化,生物学,化学,物理,等等。在本节中,我们将运用归约方法,对于从图论到集合划分的各种问题进行NP完全性的证明。

图34-13给出了在本节和34.4节中进行的NP完全性证明的流程结构。图中每种语言都含有指向它的语言,我们把该语言进行归约,从而证明其所指向语言的NP完全性。其根为CIRCUIT-SAT,我们在定理34.7中已经证明了它是NP完全语言。

《算法导论》第三十四章(续5)

34.5.1团问题

无向图G=(V,E)中的(clique)是一个顶点子集V'V,其中每一对顶点之间都由E中的一条边来连接。换句话说,一个团是G的一个完全子图。团的规模是指它所包含的顶点数。团问题是关于寻找图中规模最大的团的最优化问题。作为判定问题,我们仅仅要考虑的是:在图中是否存在一个给定规模为k的团?其形式定义为:

CLIQUE={<G,k>:G是一个包含规模为k的团的图}

要确定具有|V|个顶点的图G=(V,E)是否包含一个规模为k的团,一种朴素算法是列出V的所有k子集,并对其中的每一个进行检查,看它是否形成一个团。该算法的运行时间是Ω(k2 "')。如果k为常数,那么该算法是多项式时间的。但是,在一般情况下,k可能接近于|V|/2,这样一来,算法的运行时间就是超多项式时间。事实上,团问题的有效算法是不大可能存在的。

定理34.11  团问题是NP完全的。

证明  为了证明CLIQUE∈NP,对一个给定的图G=(V,E),用团中顶点集V'V作为G的一个证书。对于任意一对顶点u,v∈V',通过检查边(u,v)是否属于E,就可以在多项式时间内确定V'是否是团。

下一步来证明3-CNF-SAT≤pCLIQUE,以此来说明团问题是NP难度的。从某种意义来说,我们能证明这一结论是令人惊奇的,因为从表面上看,逻辑公式与图几乎没有什么联系。

该归约算法从一个3-CNF-SAT的实例开始。设Φ=C1ΛC2ΛΛCK是3-CNF形式中一个具有k个子句的布尔公式。对r=1,2,…,k,每个子句Cr,中恰好有3个不同的文字l1r、l2r、和l3r。我们将构造一个图G使得Φ是可满足的,当且仅当G包含一个规摸为k的团。

我们按照以下要求构造图G:对Φ中的每个子句Gr,=(l1V l2V l3r),我们把3个顶点v1、v2和v3组成的三元组放入V中。如果下列两个条件同时满足,就用一条边连接顶点vir和vj3 ;。

.vir和vjs处于不同的三元组中,即r≠s。

·它们的相应“文字”是一致的,即Iir不是Ijs的非。

根据Φ可以很轻易地在多项式时间内计算出该图。通过以下例子来说明这一构造过程。如果有:

Φ=(x1 V xV x3Λ (x1V x2V x3Λ (xV x2 V x3

则G就是图34-14所示的图。

《算法导论》第三十四章(续5)

该公式的一组可满足赋值为x2=0,x2=1,x1为0或者1。这一赋值以x2满足C1,以x3满足C2和C3,与浅阴影顶点所构成的团集相对应。

我们必须证明从Φ到G的转换过程是一种归约过程。首先,假定Φ有一个可满足性赋值。那么,每个子句Cr至少包含一个文字,将此文字赋值为1,并且把每个这样的文字对应于一个顶点vir。从上述的每个子句中挑选出一个这样的“真”文字,就得到k个顶点组成的集合V'。可以断言V'是一个团。对于任意的两个顶点vir,vjs ∈V'(r≠s),根据给定的可满足性赋值,两个顶点相应的文字lir和ljs都被映射为1,这两种文字不可能是互补的关系。因此,根据G的构造,边(vir,vjs)∈E。

反之,假定G有一个规模为k的团V'。G中没有连接同一个三元组中的顶点的边,因此,V'中恰好包含每个三元组的一个顶点。我们可以把每个满足vir∈V'的文字lir赋值为1,并且不必担心会出现一个文字与其补同时为1的情况,这是因为在G中,不一致文字之间不存在连线。由于每个子句都是可满足的,因此Φ也是可满足的。(不与团之中顶点相对应的变量可以随意设置。)

在图34-14的例子中,Φ的一个可满足性赋值为工x2=0,x3=1。规模为3的相应团由对应于第一个子句中的x2、第二个子句中的x3和第三个子句中的x3的顶点所组成。由于该团不包含对应于x1x1的顶点,因此,在这个可满足性赋值中,可以将x1设置为0或1。

注意在定理34.11的证明中,我们将3-CNF-SAT的任意一个实例归约成了具有某种特定结构的CLIQUE的实例。从表面上看来,似乎是我们仅证明了CLIQUE在有些图中是NP难度的在这些图中,顶点被限制为以三元组形式出现,且同一三元组中的顶点之间没有边。事实上,我们的确仅证明了CLIQUE在这种受限的情况下才是NP难度的,但是,这一证明足以证明在一般的图中,CLIQUE也是NP难度的。这是为什么呢?如果有一个能在一般的图上解决CLIQUE问题的多项式时间算法,那么它就能在受限的图上解决CLIQUE问题。

另一方面,将带有某种特殊结构的3-CNF-SAT的实例归约为一般性的CLIQUE的实例还不够。为什么这么说呢?有可能我们选择来进行归约的3-CNF-SAT的实例比较容易,因而无法将一个NP难度的问题归约为CLIQUE。

另外,还要注意一下3-CNF-SAT的实例中所用到的归约,而不仅是它的解决方案。如果多项式时间的归约的前提是已经知道公式是否是可满足的,则会导致错误,因为我们并不知道如何在多项式时间内判定Φ是否是可满足的。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~