3 P、NP问题

3.1 P(polynomial time)问题

对于一个计算问题,将其输入编码成有穷的二进制串s。判定问题接收输入串s,并返回“yes”或者“no”。这个返回值记为A(s)。若存在多项式函数p,使得对每一个输入串s,算法A对s的计算至多在O(p(|s|))步终止,则称A有多项式运行时间。==P问题就是能在多项式时间内解决的问题==。P指Polynomia。

3.2 NP(nondeterministic polynomial time)问题

为了验证一个一个解,需要输入串s以及另外的“证书”串t。如果下述两条性质成立,则称B是问题X的有效验证程序:
(1)B是有两个输入变量s和t的多项式时间算法。
(2)存在多项式p使得对每一个输入串s,A(s)=yes当且仅当存在串t使得|t|≦p(|s|)且B(s,t)=yes。
==NP问题就是能在多项式时间验证答案正确与否的问题,即所有存在有效验证程序的问题的集合==。

3.3 P问题与NP问题的关系

定理5.P \subseteq NP.
即,所有的P问题都是NP问题。当一个问题是P问题时,我们可以在多项式时间内求出问题的解。若要验证一个解(记为t1)是否正确时,只需使用多项式时间求解出这个问题的解(记为t2),然后将t1和t2做比较即可验证答案是否正确。即,可以利用多项式时间验证答案正确与否。因此,P问题也是NP问题。可以看到,三元可满足性问题(3-SAT)、独立集问题、集合覆盖问题都是NP问题。
【讨论:P=NP?】
对于这个问题,还没有人利用一种有效的方法证明。目前计算机界普遍相信P≠NP。所以P问题是NP问题的真子集。

4 NPC问题(NP完全问题)

在是否P=NP的问题没有进展的情况下,人们转向一个相对的,更加好处理的问题:哪些是NP中最难的问题?

4.1 NPC(NP-Complete)问题

若一个问题X是NP问题,且对于所有的 Y \in NP,Y \leq_p X 。即NP中的每一个问题都可以归约到X,则称问题X是NP完全问题。
✿于是,可以得到,如果NP中有一个问题不是多项式时间内可以解决的,则所有的NP完全问题都不是多项式时间内可以解决的。
并且,如果 Y 是一个 NP 完全问题, X 属于 NP ,且 Y \leq_p X,则 XNP 完全的。

4.2 电路可满足性问题是NPC问题

【电路可满足性问题】
电路可满足性问题(Circuit satisfiability problem)描述为:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。
在这里插入图片描述
图5 电路可满足性问题
图中的左边,从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候,输出为1。即这个电路是满足的。
定理6.电路可满足性问题是NPC问题。
电路可满足性问题是NPC。这个定理是Cook和Levin于1971年提出的。
证明电路可满足性问题是NPC的,根据NPC定义,需要证明以下两点:
(1)电路可满足性问题是NP问题。
(2)所有的NP问题都可以归约到电路可满足性问题。
证明:
(1)对于电路的每一个输入,只需要验证其结果是否是1即可。因此能够在多项式时间内验证答案是否正确。即电路可满足性问题是NP问题。
(2)对于一个问题,可以将输入的实例s和证书t,构造一个输入长度为(|s|+|t|)的电路。即有(|s|+|t|)个源结点(输入结点)。很容易看到,一定有办法设计电路,使得电路的输出为1。即电路是可满足的。表明所有的NP问题都可以归约为电路可满足性问题。
因此,电路可满足性问题是NPC问题。

4.3 三元可满足性问题是NPC问题

定理7.如果 Y 是一个 NP 完全问题, X 属于 NP ,且 Y \leq_p X,则 XNP 完全的。
之前已经证明3-SAT是一个NP问题,可以通过证明电路可满足性 \leq_P 3-SAT,来证明它是NP完全的。
【电路可满足性 \leq_P 3-SAT】
对于一个电路K,对于电路的每一个结点v,关联一个变量x_v , x_v表示在该结点的真值。电路K的门计算有3种:与、或、非。
如果某个结点v是非门,则它的唯一进入边来自于结点u,那么必须要有x_v= \overline x_u,可以通过添加两个子句(x_v \vee x_u)或(\overline x_v \vee \overline x_u)来保证这一点。
如果某个结点v是或门,则它的2个边分别来自于结点u和w,那么必须要有x_v= x_u \vee x_w,可以通过添加三个子句(x_v \vee \overline x_u)、(x_v \vee \overline x_w)或(\overline x_v \vee x_u \vee x_w)来保证这一点。
如果某个结点v是与门,则它的2个边分别来自于结点u和w,那么必须要有x_v= x_u \wedge x_w,可以通过添加三个子句(\overline x_v \vee x_u)、(\overline x_v \vee x_w)或(x_v \vee \overline x_u \vee \overline x_w)来保证这一点。
对于源结点,保证其等于规定的值,可以对每个源结点v添加一个只含有一个项x_v\overline x_v的子句,强迫其取规定的值。对于输出结点,添加一个单变量子句,让其取1。于是完成了构造。
可以证明构造的SAT实例是等价于与给定的电路可满足性实例的。
由于我们要证明电路可满足性 \leq_P 3-SAT,因此还需要将子句转换为恰好有3个变量的实例。
对于只有一个项t的子句,可以将子句替换成(t \vee z_1 \vee z_2);
对于有2个项的子句(t \vee t’),可以替换成(t \vee t’ \vee z_1)。
显然,为了保证新构造的子句等价于原来的子句,需要保证z_1=z_2=0
为了保证z_1=z_2=0,对于i=1和2,可以添加子句(\overline z_i \vee z_3 \vee z_4),(\overline z_i \vee \overline z_3 \vee z_4),(\overline z_i \vee z_3 \vee \overline z_4),(\overline z_i \vee \overline z_3 \vee \overline z_4),保证z_1=z_2=0
从而完成了电路K到3-SAT的构造。因此电路可满足性 \leq_P 3-SAT。证毕。
因此,根据3-SAT \leq_p 独立集 \leq_p 顶点覆盖 \leq_p 集合覆盖,可以得到独立集、顶点覆盖、集合包装、集合覆盖问题都是NPC问题。

4.4 证明NPC问题的通用策略

给定一个基本的问题X,证明其是NPC的基本策略是:
(1)证明X是一个NP问题。
(2)选择一个已知的NPC问题Y。
(3)证明Y \leq_p X

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。