数学在人类历史发展和社会生活中发挥着不可替代的作用，也是研究和学习现代科学技术不可或缺的基本工具。在漫长的岁月里，有十道数学题，永远像数学皇冠上的宝石，像数学殿堂的高墙。它们既对人类有无限的吸引力，又总是令人费解，折磨着人类的好奇心和好奇心，挑战着人类的智慧。然后今天的民族文化将向你介绍世界上最难的数学问题。（部分图文无关）

NP完全问题（NPC问题）

NP完全问题(NP-C问题)是世界七大数学问题之一。NP的英文全称是非确定性多项式的问题，即多项式复杂度的不确定性问题。简单的写法就是NP=p？问题是NP等于p还是NP不等于p。

NP是一个非确定性多项式问题，即多项式复杂度的不确定性。如果任何一个NP问题都可以通过多项式时间算法转化为NP问题，那么这个NP问题就叫做非确定性多项式完全问题。NP完全问题也叫NPC问题。

有些计算问题是确定性的，比如加减乘除等等。你只需要按照公式，一步一步的推导，就可以得到结果。但是有些问题是不能直接一步步算出来的。比如求大素数的问题。有没有一旦嵌入就可以逐步计算的公式？下一个素数应该是多少？没有这样的公式。比如一个大的合成数分解一个质因数，有公式吗？代入合成数后可以直接算出它的因子是什么？没有这样的公式。

这个问题的答案不能直接计算，只能通过间接的“猜测”得到。这就是不确定性的问题。这些问题通常都有一个算法，不能直接告诉你答案，但是可以告诉你一个可能的结果是正确的还是错误的。这个算法可以告诉你“猜测”的答案是否正确，如果能在多项式时间内计算出来，就叫做多项式不确定性问题。如果这个问题所有可能的答案都可以在多项式时间内查出来，那就叫完全多项式不确定问题。

完全多项式的不确定性问题可以用穷举法来解答，逐一检验即可得出结果。但是这样一个算法的复杂度是指数的，所以计算时间随着问题的复杂程度成指数增长，很快就变得不可数。

人们发现，所有的完全多项式不确定性问题都可以转化为一种逻辑运算问题，称为满足问题。既然这类问题所有可能的答案都可以在多项式时间内计算出来，那么人们就怀疑这类问题是否有一种确定性算法，可以在多项式时间内直接计算或搜索到正确答案。这就是著名的NP=p？猜想。

解决这个猜想只有两种可能。一个是找到这样的算法。只要为一个特定的NP完全问题找到一个算法，所有这样的问题都可以很容易地解决，因为它们可以转化为同一个问题。另一种可能是不存在这样的算法。那么就需要证明为什么在数学理论中不存在。

当今时代，在纯粹的科研、通信、交通、工业设计、企业管理部门，社会军事、政治、商业斗争中涌现出大量的NP问题。如果用纯数学家熟悉的经典穷举法求解，计算时间很容易达到天文数字，完全没有实用价值。

所以很多有数学经验的人认为，没有完整、准确、不太慢的算法可以解决这些问题。所以，NP=p？可能是本世纪最重要的数学问题。

你可能还喜欢：

谁说女性不如男性中国历史十大女政治家

你知道中国的四大文化遗产吗

自然美，盘点世界十大台球女神

中国历史上一个性格坚强的女英雄永远不会失去一个男人