NP完全问题
NP完全问题概述
NP完全问题是不确定性图灵机在P时间内能解决的问题,是世界七大数学难题之一。 NP完全问题排在百万美元大奖的首位,足见他的显赫地位和无穷魅力。 数学上著名的NP问题,完整的叫法是NP完全问题,也即“NP COMPLETE”问题,简单的写法,是 NP=P?的问题。问题就在这个问号上,到底是NP等于P,还是NP不等于P。证明其中之一,便可以拿百万美元大奖。 这个奖还没有人拿到,也就是说,NP问题到底是Polynomial(意思是多项式的),还是Non-Polynomial,尚无定论。 NP里面的N,不是Non-Polynomial的N,是Non-Deterministic(意思是非确定性的),P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。
非确定性问题详解
什么是非确定性问题呢?有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。 这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,就叫完全多项式非确定问题。 完全多项式非确定性问题可以用穷举法得到答案,一个个检验下去,最终便能得到结果。但是这样算法的复杂程度,是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可计算了。
解释
人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们于是就猜想,是否这类问题,存在一个确定性算法,可以在多项式时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。
方法
解决这个猜想,无非两种可能,一种是找到一个这样的算法,只要针对某个特定NP完全问题找到一个算法,所有这类问题都可以迎刃而解了,因为他们可以转化为同一个问题。另外的一种可能,就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。 前段时间轰动世界的一个数学成果,是几个印度人提出了一个新算法,可以在多项式时间内,证明某个数是或者不是质数,而在这之前,人们认为质数的证明,是个非多项式问题。可见,有些看来好象是非多项式的问题,其实是多项式问题,只是人们一时还不知道它的多项式解而已。 如果判定问题π∈NP,并且对所有其他判定问题 π∈NP,都有π'多项式变换到π(记为π'∞π),则称判定问题π 是NP完全的。 对P类,NP类及NP完全问题的研究推动 了计算复杂性理论的发展,产生了许多新概念,提出了许多新方法。但是还有许多难题至今没有解决,P=NP?就是其中之一。许多学者猜想P≠NP,但无法证明。
|
转自: http://hi.baidu.com/%C4%AB%D4%C2%C7%E5%C7%EF/blog/item/63bbef80f6ad84b26d81190e.html
分享到:
相关推荐
千禧年七大数学难题是21世纪初,克雷数学研究所为推动数学研究的重大进步而提出的七个极具挑战性的数学问题,每个问题悬赏一百万美元。这些问题涵盖了数学的多个分支,包括计算复杂性理论、几何学、代数和数论等。...
【世界七大数学难题】是2000年美国克雷数学研究所提出的七个极其复杂的数学问题,每个问题的解决都有可能获得一百万美元的奖金。这些问题旨在推动数学理论的发展,特别是那些数学家长期以来梦寐以求而尚未解决的难题...
本章介绍了一个极为重要的概念——NP-完全(NP-Completeness)。这一概念不仅对理论计算机科学至关重要,而且对于理解和解决实际中的复杂问题也有着深远的影响。 #### 二、可解性与不可解性 首先,我们来探讨算法的...
算法设计与分析:NP完全问题 NP完全问题是计算机科学中一个非常重要的...解决NP完全问题可以带来非常大的经济收益和社会效益。 NP完全问题是计算机科学中一个非常重要的概念,它有广泛的应用前景和深远的理论价值。
NP完全问题在计算机科学中是复杂性理论的一个重要概念,主要涉及算法的效率和问题的解法。在处理这些问题时,我们关注的是能否在合理的时间内找到解决方案。本课件聚焦于理解NP完全问题的原理及其对实际问题的影响。...
难题”之一:P(多项式算法)问题对NP(非多项式算法)问题 难题”之二: 霍奇(Hodge)猜想 难题”之三: 庞加莱(Poincare)猜想 难题”之四: 黎曼(Riemann)假设 难题”之五: 杨-米尔斯(Yang-Mills)存在性...
本资源总结了算法设计技巧与分析的第九讲 NP 完全问题,涵盖了 NP 完全问题的概念、P 类、NP 类、co-NP 类、NPI 类、判定问题和最优化问题等。 NP 完全问题是在计算机科学中一个非常重要的概念,它们是一类问题,...
【算法10_NP完全问题1】主要探讨的是计算机科学中的一个重要理论领域——NP完全问题。NP完全问题涉及的是在多项式时间内难以解决的一类决策和优化问题,这些问题的复杂性在于,虽然验证一个解决方案可以在多项式时间...
NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。
特别是在应用数学领域,如何将抽象的数学理论融入到现实世界中的问题解决,是教育者需要考虑的重要课题。本文档以“基于Python语言的应用数学案例教学——以线性代数为例”为题,探讨了如何通过Python程序语言来实现...
这七个被称为“千禧年大奖难题”的数学难题,则是从这些问题中精选出的,每个都具有深远的影响和未解的复杂性。 第一个问题是P(多项式算法)对NP(非多项式算法)问题,这是一个关于计算复杂度理论的核心问题。...
NP完全问题的概述,包括P类、NP类、CNP类问题的介绍。
这些问题是非确定性多项式时间(NP)类中的难题,因为它们在最坏情况下需要指数时间才能解决,即使使用非确定性图灵机。本压缩包“若干NP完全问题的特殊情形.rar”可能包含对一些经典NP完全问题的特定情况分析,这些...
### 论文《若干NP完全问题的特殊情形》知识点总结 #### 一、论文概览 - **标题**: 《若干NP完全问题的特殊情形》 - **作者**: 王晓东 - **出处**: 福州大学学报(1999年第27卷第5期) - **摘要**: 该论文主要讨论了...
分治法是一种重要的算法设计策略,其基本思想是将大问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题,然后递归地解决这些子问题,最后将子问题的解合并得到原问题的解。典型的分治法应用包括排序算法...
NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。
这个问题在地图绘制、资源分配等问题中有实际应用,但由于其NP完全属性,对于大规模图的着色问题,通常需要借助近似算法或启发式方法来求解。 NP完全问题的理论研究对计算机科学产生了深远的影响。一方面,它为判断...
《具体数学——计算机科学基础》是一本专门为计算机科学领域量身定制的数学教材,由格里高利·查尔斯·雷德菲尔德所著,并在2013年由人民邮电出版社出版。这本书旨在帮助计算机科学的学生和从业者理解并应用那些在...