算法设计与分析-NP完全理论

NP完全理论通向$1,000,000之路?2Overview多项式时间算法对任何规模为n的实例，这些算法的最坏情形时间复杂度为O(nk)，其中k为常数。停机问题指数级时间算法容易的和困难的问题一些有趣的问题最短简单路径vs.最长简单路径问题欧拉回路vs.汉密尔顿回路2-SAT问题vs.3-SAT问题等3判定问题最优化问题问题的每个可行解都对应一个目标函数值，求解这类问题的目的是希望得到一个有最优目标函数值的可行解判定问题回答是否存在一个满足问题要求的解，即解只是简单的回答“是(1)”或“否(0)”。最优化问题与它相应的判定问题具有密切的联系，通过限界最优化问题要优化的目标函数值，通常可以把一个最优化问题转化为一个判定问题。例如，最短路径问题的目标是找一条从u到v的最短路径，优化的目标函数值是路径的边数。则相应的判定问题(Path)可以描述为：给定一个有向图G，顶点u和v，以及整数k，问图中从u到v是否存在一条最多k条边的路径。4约简(Reduction)实例:具体问题的输入多项式约简算法:一个过程能转化A的任何一个实例α到B的某个实例β，且过程具有下列性质:（1）该转化过程只需要多项式时间就可以完成；（2）答案是一致的。也就是说，α的答案是“是”当且仅当β的答案也是“是”。5约简6在多项式时间内判定问题A的方法1）任给问题A的一个实例α，用一个多项式时间约简算法把它转化为问题B的一个实例β；2）对实例β，调用判定B的多项式时间算法；3）用β的答案作为α的答案。7用多项式时间约简算法的思想来证明特定的问题B不存在多项式时间算法假设我们有一个判定问题A，而且我们知道不存在求解A的多项式时间算法。假设有多项式时间约简算法可以把A的任意一个实例转化为B的一个实例这样我们可以用简单的反证法来证明B没有多项式时间的算法。证明的思路是，假设B有多项式时间算法，则按照上述约简算法的思想，我们也能证明A也有多项式时间算法，这与已知不存在求解A的多项式时间算法矛盾。811.2P和NP写一个程序来求解一个最优化问题，作为程序输入的问题实例必须表示成计算机能够理解的符号形式。具体问题问题实例编码成一个二进制串，由这些问题实例构成的问题给定具体问题的一个实例I，令实例的规模为n=|I|，一个算法在O(T(n))的时间内得出解，那么就说该算法在O(T(n))的时间内求解了一个具体问题。9一个具体问题是多项式时间可解的如果该问题存在一个多项式时间O(nk)求解算法，其中k为一个常数。因此我们可以定义复杂类P为多项式时间可解的具体判定问题的集合。10形式语言令字符集Σ是符号的一个有穷集合字符集Σ上的语言L是由Σ中字符所构成的字符串的集合。例如，给定Σ={0,1}，则L={10,11,101,111,1011,1101,10001,...}是素数的二进制表示所构成的语言。令ε表示空串，Ø表示空语言，则Σ上所有串的语言表示为Σ*。例如，Σ={0,1}，则Σ*={ε,0,1,00,01,10,11,000,...}，字符集Σ上的任一个语言L是Σ*的一个子集。11从形式语言的观点看，任何具体判定问题Q的实例集合仅仅是集合Σ*的一个子集，其中，由于Q完全被产生答案1（是）的实例所刻画，因此我们可以把Q看作是字符集Σ={0,1}上的语言L={x∈Σ*:Q(x)=1}.例如，对判定问题Path，我们可以构造相应的语言：PATH={G,u,v,k:G=(V,E)isanundirectedgraph,u,v∈V,k≥0isaninteger,andthereexistsapathfromutovinGconsistingofatmostkedges}.12形式语言的框架可以方便地表示判定问题及其相应求解算法之间的关系。定义11.1对于给定的输入串x∈{0,1}*，如果算法的输出A(x)=1，则说算法A接受串x。算法A所接受的串x的集合，称为算法接受的语言L={x∈{0,1}*:A(x)=1}。如果A(x)=0，则算法拒绝串x。从定义11.1可以看出，即使算法A接受一个语言L，但是对于不属于L的串x，算法不一定拒绝串x，例如算法A可能永远循环下去。13定义11.2如果算法A接受L中的每个串x，且算法A拒绝不在L中的串x，则说算法A能够判定语言L。如果算法A接受语言x，且对于任意的x∈L，能够在多项式时间O(nk)(n为串的长度，k为一个常数)内接受x，则说算法A在多项式时间内接受语言L。如果算法能够在多项式时间O(nk)(为串的长度，为一个常数)内正确判定x是否属于L，则说算法A在多项式时间内判定语言L。从上面的定义可以看出，算法接受一个语言，算法只考虑语言中的串，而判定一个语言，则需要考虑属于中的串以及不属于中的串。14现在，我们形式化的定义复杂类为语言的集合，成员资格由某种复杂类的度量来确定，例如判定一个给定串是否属于语言所需要的运行时间。定义11.3P={L∈{0,1}*:thereexistsanalgorithmAthatdecidesLinpolynomialtime}由定义11.3可知，P类是由所有可以在多项式时间内所判定的问题组成。事实上，P也是在多项式时间内所接受语言的集合。定理11.1P={L:Lisacceptedbyapolynomial-timealgorithm}.1511.2PandNP汉密尔顿回路无向图G=(V,E)的汉密尔顿回路是通过V中每个顶点恰好一次的简单回路。汉密尔顿图(hamiltoniangraph)是存在汉密尔顿回路的图。汉密尔顿回路问题给定一个无向图，它含有汉密尔顿回路吗?这个问题已经研究了上百年。现在可用语言HamCycle定义该问题如下：HamCycle={G:Gisahamiltoniangraph}.一个算法是怎样判定语言HamCycle？16验证算法定义验证算法A为带两个参数的算法。一个参数是给定的输入串x（即输入实例），另一个参数是一个证书y（即解）。如果存在一个证书y，使得A(x,y)=1，则说算法A验证了输入串x。因此，我们可以定义能够被算法A所验证的语言L={x∈{0,1}*:thereexistsy∈{0,1}*suchthatA(x,y)=1}.直观地说，如果对任何的串x，存在证书y，能够用该证书证明x∈L，而且，对任何x∉L，没有证书能够证明x∈L，则说算法验证了语言。17复杂类NP定义11.4复杂类NP指的是一类能够被多项式时间验证算法所验证语言的集合。一个语言L属于NP当且仅当存在有两个输入的多项式时间算法A和常数c，使得L={x∈{0,1}*:thereexistsacertificateywith|y|=O(|x|c)suchthatA(x,y)=1}.意思是说，算法A在多项式时间内验证了语言L。现在我们知道，NP问题中包括了P问题，即如果L∈P，则L∈NP，即PNP，也就是说，NP问题中有些问题是容易的。是否NPP成立是不知道的，但是大多数的研究者相信，P和NP不同类，即P≠NP。NP类由那些其解能很快验证的问题所构成。从我们的直觉和经验，我们知道，解一个问题比验证该问题的解要困难得多。很多理论计算机科学家相信，NP确实包括一些不属于P的语言，即NPC。一个有趣的问题，令co-NP={NP}，即NP类在补运算下是否封闭的问题。例如，HamCycle∈NP，HamCycle的补问题可以描述如下，对于给定的一个无向图，不存在一条汉密尔顿回路吗？co-NP是否等于NP的问题，也仍然悬而未决，但是大多数研究者相信co-NP≠NP。$1,000,000problemP=NP?Solved???!!!!•$1,000,000offeredbyClayMathematicalInstituteTheFutureP=NP?2111.3NP-completeness(NPC)大多数理论计算机科学家相信P≠NP是因为他们确实找到一类问题NPC，这类问题有令人非常惊奇的性质，即如果NPC中任何一个问题能够在多项式时间内求解，则NP中的每个问题都能多项式时间求解，即P=NP，尽管研究了大半个世纪，但是还没有找到任何一个NPC问题的多项式时间算法。为什么研究NP-completeness?能够显示一个问题确实很难最好寻找近似算法来求解许多有趣的实际问题事实上是NPC.怎么样比较语言(问题)的相对难度?22约简定义11.5给定一个函数f:{0,1}*→{0,1}*，对任意给定的x∈{0,1}*，如果存在一个多项式时间算法A，A产生输出f(x)，则称f是多项式时间可计算的。定义11.6给定语言L1和L2，如果存在多项式可计算的函数f:{0,1}*→{0,1}*使得对任意的x∈{0,1}*，x∈L1当且仅当f(x)∈L2，则说语言L1能多项式时间约简到L2，记为L1≤PL2。函数称为约简函数。计算函数f的算法称为约简算法。23图11.2描述了将一个语言多项式时间约简到语言的例子。约简函数f提供了一个多项式时间映射使得如果x∈L1，则f(x)∈L2。而且如果x∉L1，则f(x)∉L2。这样约简函数f将由语言L1表示的判定问题的任何实例x映射到由L2表示的判定问题的一个实例f(x)。因而，是否f(x)∈L2的答案提供了是否x∈L1的答案。f{0,1}*{0,1}*24FA2yes,f(x)∈L2no,f(x)∉L2yes,x∈L1no,x∉L1A1xf(x)引理11.1如果语言L1,L2∈{0,1}*使得L1≤PL2，且L2∈P，则L1∈P证明：令A2是判定L2的多项式时间算法，令A是计算从L1到L2约简函数f的多项式时间约简算法，为了证明该引理，只需构造一个能够判定L1的多项式时间算法A1即可。25NP-completeness多项式时间约简提供了一种证明一个问题至少与另一个问题一样难的形式化方法定义11.7给定语言L{0,1}*，L是NP完全的（NP-complete）当且仅当(1)L∈NP；(2)对于所有L'∈NP，有L'≤PL。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言L是NP难的（NP-hard）。并记NPC表示所有NP完全语言构成的语言类。NPC是NP中最难的问题。26定理11.2如果任何一个NPC问题多项式时间可解，则P=NP。等价地，如果NP中的任何问题没有多项式时间求解算法，则没有NPC问题是多项式时间可解的。PNPNPCNP-hard27电路可满足性问题CircuitsatisfiabilityNOTORANDLogicGates:Inputs:01011111Output:01001布尔电路是一个无环的有向图，图中每个顶点对应一个逻辑门，它对应简单的布尔函数，例如NOT、AND和OR。逻辑门的入边是其相应布尔函数的输入，如果入边的起点没有连接到一个逻辑门，则该入边为布尔电路的输入。逻辑门的出边是其相应布尔函数的输出，如果一个输出的终点不再连接到一个逻辑门，则它称为整个布尔电路的输出。具有一个输出的布尔组合电路是可满足的，指的是它有一组可满足的赋值，使得组合电路的输出为1。电路可满足性(CircuitSatisfiablity，简记CircuitSAT)问题指的是，给定一个由逻辑门AND、OR和NOT构成的组合电路C，它可满足吗?从形式语言的角度，可以定义如下CircuitSAT={C:Cisasatisfiablebooleancombinationalcircuit}29NOTORANDLogicGates:Inputs:01011111Output:01001引理11.2CircuitSAT属于NP30Cook-LevinTheorem引理11.3CircuitSAT是NP难的。证明：令L是NP中的任何一个语言，我们将描述一个多项式时间