8.3证明NP完全问题 
 （1) Problem： 
 STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY SAT is NP-complete. 
 （2) Solution： 
 类似于SAT问题，显然对于给定的一组变量赋值，我们可以在多项式时间内证明是否为STINGY SAT问题的解，所以STINGY SAT问题是NP问题； 
 SAT问题是给定一个CNF，给出一组变量值使得所有字句为真，或者证明不存在满足的解。令k = n时，可以将SAT问题归约成STINGY SAT问题，由于SAT问题是NP完全问题，所以STINGY SAT问题也是NP完全问题。
 
8.10证明NP完全问题 
 （a）子图同构：令G是一个环，且环上的顶点数等于H上的顶点数。如果G是H的同构子图，则H中存在Rudrata回路，Rudrata回路问题是子图同构问题的一个特例，所以子图同构问题也是一个NP完全问题； 
 （b）最长路径：假设G=(V, E)，g=|V|-1，则G中存在Rudrata路径，Rudrata路径问题是最长路径问题的一个特例，所以最长路径问题也是一个NP完全问题； 
 （c）最大SAT：与8.3的问题相似，令g等于CNF中字句的个数时，则SAT问题可归约成最大SAT问题，所以最大SAT问题也是一个NP完全问题； 
 （d）稠密子图：令b=a(a-1)/2，则此时图G中的a个顶点两两相连，最大团问题是此问题的一个特例，所以稠密子图问题是一个NP完全问题； 
 （e）稀疏子图：令b=0，则此时图G中的a个顶点两两互不相连，最大独立集是此问题的一个特例，所以稀疏子图问题是一个NP完全问题； 
 （f）集覆盖：集合覆盖是指从B={b1, b2, b3, …, bn}中找出一组集合使得其并集等于集合A，而顶点覆盖是指从V中找出一组顶点V’使得G中的每条边至少有1个顶点在V’中，最小顶点覆盖可以看成是集合覆盖的一个特例，所以集合覆盖也是一个NP完全问题； 
 （g）可靠网络：TSP问题是此问题的一个特例，所以可靠网络问题是一个NP完全问题。
 
8.14证明NP完全问题 
 （1）Problem： 
 Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and an integer k, return a clique of size k as weill as an independent set of size k, provided both exist. 
 （2）Solution： 
 独立集问题和团集问题是等价的，假设要求图G中存在大小为k的团集，可以向原图G中增加k个互相独立的顶点，则这k个顶点构成了新图G大小为k的独立集，同时也不影响原图的团，团集问题可归约成此问题，因此该问题是NP完全问题。
 
8.15证明NP完全问题 
 （1）Problem： 
 Show that the following problem is NP-complete. 
 MAXIMUM COMMON SUBGRAPH 
 Input: Two graphs G1=(V1,E1) and G2=(V2,E2);a budget b. 
 Output: Two set of nodes V1’⊆V1 and V2’⊆V2 whose deletion leaves at least b nodes in each graph, and makes the two graphs identical. 
 （2）Solution： 
 假设G1=(V, E), G2=(V, Ø)，当存在至少b个顶点的最大公共子图时，即存在至少b个顶点的独立集。 
 a. 如果有图大小为b的最大公共子图，且这b个顶点不属于独立集，则至少有2个顶点有边相连，G1和G2的子图中这两个顶点就是相连的，而因为假设条件中G2是不存在边的，出现矛盾，因此这b个顶点属于独立集； 
 b. 如果有b个顶点属于独立集，我们取这b个顶点构成G1和G2的子图，所以G1中这b个顶点之间不存在边，G2又是没有边的图，所以这两个子图就是相同的，也就是存在大小为b的公共子图。 
 因此，独立集问题是这个问题的一个特例，这个问题就是NP完全问题。

NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。
 
根据这个概念，要证明一个问题是NP类的，第一证明此问题是不确定的；第二证明此问题可在多项式时间求解
 
这是我的理解，你可以参考一下
  

 
 
8.3
 
 
STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an 
 
 
integer k, find a satisfying assignment in which at most k variables are true, if such an assignment 
 
 
exists. Prove that STINGY SAT is NP-complete.
 
 
证明：
 
 
由于可以在多项式时间内验证STINGY SAT的解，所以该问题属于NP问题。而将k设为所有变量的总数
 
 
时，就可以将SAT规约到STINGY SAT，因此该问题为NP完全问题。
 
 
 
 
 

 
8.8
 
 
In the EXACT 4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly
 
 
four literals, and such that each variable occurs at most once in each clause. The goal is to find a
 
 
satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete.
 
 
证明：
 
 
由于可以在多项式时间内验证EXACT 4SAT的解，因此该问题属于NP问题。为证明其NP完全性，考虑
 
 
通过将3SAT规约到EXACT 4SAT。对于任意一个3SAT实例，如果其中某个子句中包含同一个literal多次，
 
 
那么可以把这个多次出现的literal缩减为一次；如果同时包含某个literal的肯定和否定，则可以去掉它。另
 
 
外，可以在每个子句中添加一些哑变量（辅助变量，没有实际用处），这样就可以将每个子句中包含的
 
 
literal的数目增加到四个。因此，该3SAT实例可以转化为一个EXACT 4SAT问题。因此，可以证明该问
 
 
题是NP完全的。
 
 
 
 
 
转载于:https://www.cnblogs.com/pxy7896/p/7117207.html

 
2020年7月出版的《计算机科学》(中国计算机学会会刊)发表了国防科技大学教授、湘潭大学计算机学院特聘教授姜新文题为《哈密顿图判定问题的多项式时间算法》的论文,这标志着在数学和计算机科学领域中最为重要的难题之一"NP=P?"得到科学证明,论文刊出几天后下载量近千次,引发有关学术群体热议。
 

 
"NP=P?"也称"NP≠P还是NP=P",实质是P对NP关系问题,被称为世界级数学难题之一。
 
2000年5月,美国克雷数学研究所(CMI)在巴黎举行的千年数学大会上宣布对攻克世界7个数学难题的悬赏。P对NP关系问题被列为新千年7大难题之首。2005年《科学》杂志将"NP=P?"问题作为数学科学的代表,列为25个学科难题之一。2018年《科学》杂志再次列出125个亟待解决的科学难题,其中第19个问题就包含"NP=P?"问题。
 
迄今为止,新千年7大数学难题中除了俄罗斯数学家佩雷尔曼2002年证明了有关拓扑学的"庞加莱猜想"之外,其他难题均悬而未决。
 
据介绍,20世纪,现代计算机问世,NP与P的关系问题就成为计算机科学和数学交叉领域的基础科学问题。通常,算法求解一个问题需要耗费时间,这被称为算法的时间复杂度。求解同一个问题的不同算法耗费的时间可能不同,只有采用多项式时间算法才能最有效解决问题。
 
NP≠P,其核心是否定不同选择方法,认为有些问题不存在多项式算法。
 
而姜新文证明了"NP=P",表明多项式算法实际上是存在的。
 
姜新文从1986年开始讲授《算法设计与分析》课程,结合此前学习图论时关于哈密顿图判定问题的思考,开始研究P对NP关系问题。9年之后,姜新文于1995年发表了研究成果《简单无向图H性质判定》,开始思考运用整体观思路来处理一个有限系统的计算问题。
 
他首先建立了一套基于数学归纳法的证明框架,然后坚持探索满足这套证明框架的算法设计。从1995年开始之后的15年中,经历了2000次以上设计、修改与调整,到2010年底得到预期效果。姜新文35年的潜心探索,终于获得成功!
 
"NP=P"得到证明具有重要的科学意义与应用价值。因为这将为计算机科学领域带来截然不同的理论极限和发展前景。在现代经济社会中,大量科研、生产、国防与社会服务过程都需要采用正确的快速计算方法。可以期待,在"NP=P时代",地球科学、生命科学、宇宙科学、环境科学、生物科技、材料工程、管理科学、数学科学、物理科学等多个学科的研究都将得到更深入的推进。
 
此外,由于现代密码学是建立在NP≠P的假定之上,而现在NP=P得到证明,对密码学的发展是一次巨大的科学挑战。
 
相关论文信息:doi: 10.11896/jsjkx.191200176