NP完全问题的最新情况
答案:1 悬赏:80
解决时间 2021-01-14 07:42
- 提问者网友：未信
- 2021-01-14 01:43
NP完全问题的最新情况
最佳答案
- 二级知识专家网友：往事埋风中
- 2021-01-14 03:09
2010年8月6日，HP LAB的 Vinay Deolalikar 教授宣布证明了P!=NP，证明文章已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（PDF格式共103页），但在8月15日，人们关于论文的看法——即证明不能成立——已经趋于稳定（当然这不能排除大家都同时犯了错误的可能性），随后的发言越来越多地集中于更抽象的层面，并且至今仍在继续。
论NP=P
NP=P，概括的说就是3句话：
1.任意简单无向图的最大团问题等于其对应的“任意两个顶点的距离不大于2的图”——可
以称之为理想图的最大团问题；
2.任意理想图的图着色问题是多项式时间问题；
3.任意理想图，其图着色问题可在多项式时间内转换为它的最大团问题。
证明大纲：
定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点， E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。 证明：显然。 推论：对任意简单无向图G=（V,E），存在简单无向图G'=(V，E')，满足： （1）E⊆E'； （2）G'中任意两个顶点的距离不大于2； （3）G'与G有相同的最大团。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大 于2，则存在n的多项式时间算法，可在该算法下，解决G的图着色问题，即确 定G的顶点色数。 证明思路与算法：易知G是k-部图（不一定、也无须是完全k-部图）。 算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的 顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1， 设V=V1∪V2,V1∩V2=Ø，G去掉V1中所有顶点（及其关联边）得到图 G2=(V2，E2)。则可以证明G2的顶点色数比G的顶点色数小1；且G2去掉度 小于2的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于2的。 由递归关系可知G的顶点色数可以在n的多项式时间内确定。
定理3.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大 于2，则G的图着色问题（顶点色数问题）可以在n的多项式时间内转换为G的 最大团问题。 证明思路：已知图着色问题≤pSAT（“≤p”表示多项式时间归约） SAT≤p 3-SAT 3-SAT≤p 团问题 只需注意细节，就可证明定理2。
论NP=P
NP=P，概括的说就是3句话：
1.任意简单无向图的最大团问题等于其对应的“任意两个顶点的距离不大于2的图”——可
以称之为理想图的最大团问题；
2.任意理想图的图着色问题是多项式时间问题；
3.任意理想图，其图着色问题可在多项式时间内转换为它的最大团问题。
证明大纲：
定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点， E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。 证明：显然。 推论：对任意简单无向图G=（V,E），存在简单无向图G'=(V，E')，满足： （1）E⊆E'； （2）G'中任意两个顶点的距离不大于2； （3）G'与G有相同的最大团。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大 于2，则存在n的多项式时间算法，可在该算法下，解决G的图着色问题，即确 定G的顶点色数。 证明思路与算法：易知G是k-部图（不一定、也无须是完全k-部图）。 算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的 顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1， 设V=V1∪V2,V1∩V2=Ø，G去掉V1中所有顶点（及其关联边）得到图 G2=(V2，E2)。则可以证明G2的顶点色数比G的顶点色数小1；且G2去掉度 小于2的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于2的。 由递归关系可知G的顶点色数可以在n的多项式时间内确定。
定理3.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大 于2，则G的图着色问题（顶点色数问题）可以在n的多项式时间内转换为G的 最大团问题。 证明思路：已知图着色问题≤pSAT（“≤p”表示多项式时间归约） SAT≤p 3-SAT 3-SAT≤p 团问题 只需注意细节，就可证明定理2。
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息！
大家都在看
推荐信息