p=np是数学问题吗

时间:2023-09-16 08:10:37 常识 我要投稿

  是。

  p=np是数学问题吗1

  事实上,现代加密技术依赖于这样一个事实:大质数不可能因式分解。这些问题似乎都有一个共同的难题,也就是P( polynomial time)对NP( non-deterministic polynomial time)谜题的核心——什么是可化简的,什么是不可化简的?

  1859年,爱尔兰数学家威廉·汉密尔顿画了一个叫做伊科希的数学游戏。这个游戏是在一个由20个角(顶点)组成的木制十二面体表面上进行的。每个角落都标上了一个城市的名字。

  游戏的目标是找到一个循环,即访问每个顶点一次,然后返回起点。这种路径称为哈密顿循环。这个简单的博弈产生了图论中的一个重要问题,即哈密顿循环决策问题——给定一个任意地图,我们如何知道它是否包含一个哈密顿循环?

  二维平面图形的十二面体。一个可能的哈密顿循环用红色表示。

  给出一个图,确定它是否包含一个哈密顿循环。

  解决这个问题的一种方法是遍历图中任何可能的路径,并检查该路径是否为哈密顿循环。然而,由于可能路径的数量可以达到n的阶乘。

image.png  

  这样,即使一个只有40个顶点的图也可能包含超过10^45条路径,使得问题几乎不可能在合理的时间内解决(即使对于最强大的处理器也是如此)。

  此外,由于顶点数量与路径数量之间的阶乘依赖关系,即使我们再增加一个顶点,也需要大幅提升计算机的'计算能力。我们可以说,阶乘增长的根本性质使这个问题比其他问题更困难。

  这就是数学问题的艰巨性——如果一个问题需要的资源随着投入的增加而急剧增加,那么这个问题就非常棘手。

  为了使这个想法形式化,计算机科学家使用了时间复杂度的尺度。时间复杂度指的是解决一个问题需要多少步长,以及所需的步长如何随问题的大小而变化。给定一个算法,算法的时间复杂度被描述为一个渐近函数,它依赖于算法的输入大小。

  渐进观点是计算复杂性理论所固有的,它揭示了有限而精确的分析所掩盖的结构——阿维·威格森

  一个算法的时间复杂度被描述为一个渐近函数,它依赖于算法的输入大小。一个主要的区别是阶乘,指数和多项式复杂度函数。

  对于具有多项式复杂度的算法和具有更基本复杂度函数的算法,有一个基本的区别。这种区别主要是由于多项式增长被认为比其他增长更为缓慢,因为增大输入不会导致所需步骤急剧增加。

  多项式(Polynom)是一种只涉及加、减、乘和非负整数指数运算的构造,因此不是指数或阶乘增长。选择多项式来表示有效的计算似乎是任意的,然而,随着时间的推移,它从许多角度证明了自己的合理性。

  例如,多项式在加法、乘法和组合下的闭包保留了自然编程实践中的效率概念,比如将程序链接到一个序列中,或者将一个程序嵌套到另一个程序中

  p=np是数学问题吗2

  具有多项式时间复杂度的算法被称为“高效”。

  多年来,为了有效地解决哈密顿循环决策问题,科学家们进行了许多尝试。其中一种是Held-Karp算法,它能在指数时间内解决这个问题。然而,没有已知的算法可以在多项式时间内解决这个问题,因此,它仍然被认为是一个难题。

  迈克尔·赫尔德,理查德·史克和理查德·卡普。

  然而,一个有趣的现象发生了,尽管我们不能有效地解决这个问题,给定一个路径图中,我们至少可以有效地检查是否是哈密顿循环,因为简单循环中的最大顶点数为n,则遍历路径所需的时间被多项式限定为n。。

  这种现象也出现在其他难题中,例如数独决策问题——给定一个不完整的数独网格,我们希望知道它是否至少有一个有效的解决方案。

  任何提出的数独解决方案都可以很容易地验证,并且随着网格的增大,检查一个解决方案的时间会多项式的增长。然而,所有已知的寻找解决方案的算法,对于困难的例子,时间会随着网格的增大呈指数增长。

  与哈密顿路径决策问题相似,目前还没有任何已知的算法可以有效地解决数独问题,但是,只要给出一个解,就可以有效地验证该解。

  似乎许多其他决策问题都具有这一特性——不管它们是否能被有效地解决,它们所提出的解决方案都能被有效地验证。这类问题被定义为NP。

image.png  

  如果一个决策问题的解能被有效地验证,那么这个决策问题就是NP问题。

  首字母缩写NP代表不确定性多项式时间(尽管人们普遍认为NP的意思是“非P”)。

  进一步思考问题的可解性与其解的可验证性之间的关系,我们可以得出下一个结论:如果一个决策问题是有效可解得,那么它的解必须是有效可验证的。

  为什么?因为如果一个决策问题是可以有效地解决的,那就意味着我们可以有效地找到它的解决方案。

  然后,给出一个解决方案,我们可以简单地通过与问题的实际解决方案比较来验证它。换句话说,生成解决方案的算法的正确性自动证明了该解决方案。

  从这个结论可以看出,很明显,NP包含的问题子集也是有效可解的。这个子集被定义为P。

  P是所有可有效解决的`决策问题的集合,是NP的一个子集。基本算法是多项式时间可解的。象棋决策问题不属于NP问题,因为没有一种有效的算法可以检查给定的棋盘是否有效。魔方决策问题属于NP问题,因为判断一个给定的魔方是否是一个解是很简单的。

  哈密顿路径决策问题有一个有效的算法可以验证它的解,因此,它属于NP。有人可能会问这个问题是否在P中,一方面,我们不知道有一个有效的算法可以解决这个问题。

  另一方面,没有证据表明这样的算法不存在。事实上,这样的算法仍然有可能存在,而且还没有被发现。数独的决策问题也是一样。

  事实上,对于许多其他主要问题,包括布尔可满足性问题,旅行推销员问题,子集和问题,派系问题,图着色问题——尽管我们已经证明这些问题是NP,但没有证据表明他们在P 。这就是P=NP问题的意义所在:

  p=np是数学问题吗3

  P和NP真的是一样的吗?

  如果是的话,这就意味着NP中的所有问题都可以被有效地解决,尽管我们仍然没有找到实现这一点的神秘算法。否则,在NP中存在一些无法有效解决的问题,任何尝试解决将意味着浪费我们的时间和精力。

  大多数时候,不能有效地解决问题是一件消极的事情。然而,在某些情况下,我们可以从问题的“硬度”中获益。属于NP而不属于P的问题,其主要特点是很难解决,但很容易验证其解决方案。

  给定两个正整数n和k,判断n是否有一个质因数小于k。——质因数分解决策问题

  由于该问题的解可以有效地验证,因此我们知道该问题属于NP,给定一个整数c,它需要“多项式时间”来知道c是否是一个比k小的质数,还是n的因数。

  但是,目前还没有一种算法可以在多项式时间内解决这一问题。因此,使用两个相当大的质数,就可以计算它们的乘法,这用于生成一个公钥和一个私钥。

  公钥可以为所有人所知,并用于加密消息。使用公钥加密的消息只能在合理的时间内使用私钥解密,假设没有有效的方法将一个大整数分解为它的质数因子。

image.png  

  RSA-2048有617位十进制数字(2048位)。它是RSA数字中最大的,因式分解获得的现金奖金最高,为20万美元。除非在不久的将来在整数因子分解或计算能力方面取得重大进展,否则RSA-2048在许多年内可能无法分解。

  但是,如果P=NP,则最后一个假设是错误的。为什么?如果P等于NP,那么质因数分解问题在P中,这意味着它可以被有效地解决。

  因此,一旦找到这样一个算法,任何公钥都可以在合理的时间内解密,而不需要私钥,这使得整个RSA密码系统完全崩溃,至少在理论上如此。

  但是P=NP的负面影响与它所具有的潜在好处相比,是无关紧要的.。在数学、优化、人工智能、生物学、物理学、经济学和工业领域中,确实存在着数以千计的NP问题,这些问题都是出于不同的需要而自然产生的,而有效的解决方案将使我们在许多方面受益。

  证明P=NP将意味着所有这些难题都可以在多项式时间内解决,这将导致在那些卓越的算法之后进行大规模的智力追求。一旦发现,这些算法将有可能推动人类的进步,远远超出我们的掌握。

【p=np是数学问题吗】相关文章:

身份证照片会帮忙p图吗09-13

对孩子打骂很凶是心理问题吗08-27

你有什么问题要问吗04-20

左撇子宝宝容易出现心理问题吗09-07

孩子打别的小朋友是心理问题吗04-12

不想结婚的人是心理有问题吗05-13

新生儿湿肺问题大吗09-11

风水真实吗:装修:如何考量风水问题08-31

男孩喜欢穿女装是心理有问题吗09-13