第十二章--NP完全问题

第十二章NP完全问题12.1P类和NP类问题12.2NP完全问题12.3co_NP类和NPI类问题12.1P类和NP类问题12.1.1P类问题12.1.2NP类问题12.1.1P类问题一、确定性算法定义12.1A是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法A是确定性的算法。算法执行的每一个步骤，都有确定的选择。重新用同一输入实例运行该算法，所得到的结果严格一致。二、P类判定问题1、定义：定义12.2如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以)(knO的时间运行一个确定性的算法，得到yes或no的答案，则该判定问题是一个P类判定问题。2、特性：P类判定问题是由具有多项式时间的确定性算法来解的判定问题12.1.1P类问题例：最短路径判定问题SHORTESTPATH：给定有向赋权图),(EVG（权为正整数）、正整数k、及两个顶点Vts,，是否存在着一条由s到t、长度至多为k的路径。可排序的判定问题SORT：给定n个元素的数组，是否可以按非降顺序排序。12.1.1P类问题三、封闭1、P类判定问题的补：改变判定问题的提法，“是否可以”、“是否存在”改为“是否不可以”、“是否不存在”的判定问题。例：可排序判定问题的补NOT_SORT：给定n个元素的数组，是否不可以按非降顺序排序。最短路径判定问题的补NOTSHORTESTPATH：给定有向赋权图),(EVG（权为正整数）、正整数k、及两个顶点Vts,，是否不存在一条由s到t、长度至多为k的路径。2、封闭的定义定义12.3令C是一类问题，如果对C中的任何问题C，的补也在C中，则称C类问题在补集下封闭。12.1.1P类问题3、P类问题的封闭性定理12.1P类问题在补集下是封闭的。证明令P类判定问题的补为；存在确定性算法A，可用多项式时间返回yes或no的答案。算法A是算法A中返回yes的代码改为返回no、返回no的代码，改为返回yes的算法。则算法A是解问题的确定性算法，可用多项式时间返回yes或no的答案。因此P类问题的补，也属于P类问题。所以，P类问题在补集下是封闭的。12.1.1P类问题四、归约1、归约的定义定义12.4令和'是两个判定问题，如果存在一个具有如下性能的确定性算法A，可以用多项式的时间，把问题'的实例'I转换为问题的实例I，使得'I的答案为yes，当且仅当I的答案是yes。就说，'以多项式时间归约于，记为p'。2、P类问题的归约性定理12.2和'是两个判定问题，如果P，并且p'，则P'。12.1.1P类问题证明因为p'，存在确定性算法A，可用多项式)(np时间，把问题'的实例'I转换为问题的实例I。使得'I的答案为yes，当且仅当I的答案是yes。如果对某个正整数0c，算法A每一步的输出，最多可输出c个符号，则算法A的输出规模，最多不会超过)(npc个符号。因为P，存在多项式时间的确定性算法B，对输入规模为)(npc的问题进行求解。所得结果也是问题'的结果。令算法C是把算法A和算法B合并起来的算法，则算法C也是确定性的算法，且以多项式时间))(()(npcqnr得到问题'的结果，所以，P'。12.1.2NP类问题一、非确定性算法1、问题的非确定性算法的两个阶段：推测阶段和验证阶段。2、推测阶段：对规模为n的输入实例x，以多项式时间)(inO产生输出y，而不管y的正确性3、验证阶段：以多项式时间)(jnO的确定性算法验证两件事情：1）检查上一阶段的输出y是否具有正确的形式。如果y不具正确的形式，算法就以答案no结束；2）如果y具有正确的形式，则继续检查y是否是问题的输入实例x的解。如果它确实是问题实例x的解，则以答案yes结束，否则，以答案no结束。12.1.2NP类问题例货郎担的判定问题：给定n个城市、正常数k、及城市之间的费用矩阵C，判定是否存在一条经过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数k的回路。令A是求解货郎担判定问题的算法。A用非确定性的方法，在多项式时间内推测存在着一条回路，假定它是问题的解，A用确定性的算法，在多项式时间内检查：该回路是否是哈密尔屯回路，如果答案为yes，则继续检查该回路的费用是否小于常数k，如果答案仍为yes，则算法A输出yes，否则输出no。因此，A是求解货郎担判定问题的非确定性算法。12.1.2NP类问题二、NP类判定问题1、定义：定义12.5如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以)(knO的时间运行一个非确定性的算法，得到yes或no的答案，则该判定问题是一个NP类判定问题。2、特性：存在确定性的算法，能够以多项式时间，来检查和验证在推测阶段产生的答案。12.1.2NP类问题例解货郎担判定问题TRAVELINGSALESMAN的算法A是NP类判定问题：A可在推测阶段用多项式时间推测出一条回路，并假定它是问题的解；在验证阶段用多项式时间的确定性算法，检查所推测的回路是否恰好每个城市经过一次，如果是，再进一步判断这条回路的长度是否小于或等于l，如果是，答案为yes，否则，答案为no。存在多项式时间的确定性算法，对推测阶段所作出的推测进行检查和验证。因此，货郎担判定问题是NP类判定问题。12.1.2NP类问题例m团问题CLIQUE：给定无向图),(EVG、正整数m，判定V中是否存在m个顶点，使得它们的导出子图构成mK完全图。在推测阶段用多项式时间对顶点集生成一组m个顶点的子集，假定它是问题的解；在验证阶段用多项式时间的确定性算法，验证该子集的导出子图是否构成mK完全图。如果是，答案为yes，否则，答案为no。存在多项式时间的确定性算法，对前面的推测进行检查和验证。因此，m团问题是NP类判定问题。12.1.2NP类问题3、P类问题和NP类问题的差别：P类问题可以用多项式时间的确定性算法来进行判定或求解；NP类问题可以用多项式时间的确定性算法来检查和验证它的解。P，必然有NP，所以，NPP。猜测PNP。该不等式是否成立、至今还没有得到证明。12.2NP完全问题12.2.1NP完全问题的定义12.2.2几个典型的NP完全问题12.2.3其他的NP完全问题12.2.1NP完全问题的定义一、NP完全问题的定义1、NP难题定义12.6令是一个判定问题，如果对NP中的每一个问题NP'，有p'，就说判定问题是一个NP难题。2、NP完全问题定义12.7令是一个判定问题，如果：(1)NP，并且：(2)对NP中的所有问题NP'，都有p'；则称判定问题是NP完全的。3、NP难题和NP完全问题的差别是NP完全问题，'是NP难题，则必定在NP类中，而'不一定在NP类中。12.2.1NP完全问题的定义二、NP完全问题的证明1、归约的传递性定理12.3令、'和''是三个判定问题，满足'''p，及p'，则有p''。证明假定问题''的实例''I由n个符号组成。因为'''p，存在确定性算法''A，以用多项式)(np时间，把问题''的实例''I转换为问题'的实例'I。使得''I的答案为yes，当且仅当'I的答案是yes。若算法''A每一步最多可输出c个符号，0c，则算法''A的输出规模，不会超过)(npc个符号。它们组成了问题'的实例'I。因为p'，存在确定性算法'A，以多项式))((npcq的时间，把问题'的实例'I，转换为问题的实例I，使得'I的答案是yes，当且仅当I的答案是yes。令算法A是把算法''A和算法'A合并起来的算法，则算法A也是一个确定性的算法，并且以多项式时间))(()(npcqnr，把问题''的实例''I转换为问题的实例I，并且使得''I的答案为yes，当且仅当I的答案是yes。由此得出，''以多项式时间归约于，即p''。例已知哈密尔顿回路问题HAMILTONIANCYCLE是一个NP完全问题，证明货郎担问题TRAVELINGSALESMAN也是一个NP完全问题。哈密尔顿回路问题：给定无向图),(EVG，是否存在一条回路，使得图中每个顶点在回路中出现一次且仅一次。货郎担问题：给定n个城市和最短距离l，是否存在从某个城市出发、经过每个城市一次且仅一次、最后回到出发城市、且距离小于或等于l的路线。1）证明货郎担问题是NP问题。例12.2中已经说明。2）证明哈密尔顿回路问题可用多项式时间归约为货郎担问题，即HAMILTONIANCYCLEpTRAVELINGSALESMAN.令),(EVG是HAMILTONIANCYCLE问题的任一实例，nV||。构造赋权图),('''EVG，使得'VV，},|),({'VvuvuE。对'E中的每一条边),(vu赋予如下的长度：EvunEvuvud),(),(1),(令nl。可以由一个算法在多项式时间里完成这个构造。因此，哈密尔顿回路问题可以用多项式时间归约为货郎担问题。3）证明G中包含一条哈密尔顿回路，当且仅当'G中存在一条经过各个顶点一次，且全长不超过nl的路径。(1)G中包含一条哈密尔顿回路，设这条回路是121,,,,vvvvn。则该回路也是'G中一条经过各个顶点一次且仅一次的回路，根据式（12.2.1），这条回路长度为n，因此，这条路径满足货郎担问题。(2)'G中存在一条满足货郎担问题的路径，则这条路径经过G中各个顶点一次且仅一次，最后回到起始出发顶点的回路，因此它是一条哈密尔顿回路。综上所述，关系HAMILTONIANCYCLEpTRAVELINGSALESMAN成立。所以TRAVELINGSALESMAN问题也是一个NP完全问题。12.2.2几个典型的NP完全问题12.2.2.1可满足性问题（SATISFIABILITY）12.2.2.2三元可满足性问题（3_SATISFIABILITY）12.2.2.3图的着色问题（COLORING）12.2.2.4集团问题（CLIQUE）12.2.2.5顶点覆盖问题（VERTEXCOVER）12.2.2.1可满足性问题（SATISFIABILITY）一、可满足性问题1、合取范式：由若干个析取子句的合取构成的布尔表达式f。例：)()()(4325431532xxxxxxxxxxf2、合取范式的可满足性：对合取范式f的相应布尔变量赋值，使f的真值为真，就说布尔表达式f是可满足的。例：上式中，只要使1x、4x和5x为真，则表达式f为真。因此，这个式子是可满足的。3、可满足性问题：判定问题：SATISFIABILITY输入：CNF布尔表达式f问题：对布尔表达式f中的布尔变量赋值,是否可使f的真值为真12.2.2.1可满足性问题（SATISFIABILITY）二、可满足性问题是NP完全的定理12.5（Cook定理）可满足性问题SATISFIABILITY是NP完全的。证明1）证明可满足性问题SATISFIABILITYNP：f是任意给定的布尔表达式，容易构造一个确定性的算法，以多项式的时间，对表达式中的布尔变量的0、1赋值，来验证布尔表达式f的真值。因此，可满足性问题SATISFIABILITYNP。2）证明对任意给定的问题NP，都有pSATISFIABILITY：因为NP，存在解问题的多项式时间的非确定性的算法A，可以用合取范式的形式构造布尔表达式f，用f模拟算法A对实例I的计算，使得f的真值为真，当且仅当问题的非确定性算法A对实例I的答案为yes。设实例I的规模为n，A可在多项式时间)(np内完成，对某个整数0c，它最多可执行的动作为)(npc个，可以用))(())((nqOnpcO的时间来构造布尔表达式f，其中，)(nq是某个多项式。因此，有pSATISFIABILITY。综上所述，可满足性问题SATISFIABILITY是NP完全