解决计算机数学中最著名的难题P=NP将彻底改变人(2)
【作者】网站采编
【关键词】
【摘要】如果一个决策问题的解能被有效地验证,那么这个决策问题就是NP问题。 首字母缩写NP代表不确定性多项式时间(尽管人们普遍认为NP的意思是“非P”)。
如果一个决策问题的解能被有效地验证,那么这个决策问题就是NP问题。
首字母缩写NP代表不确定性多项式时间(尽管人们普遍认为NP的意思是“非P”)。
进一步思考问题的可解性与其解的可验证性之间的关系,我们可以得出下一个结论:如果一个决策问题是有效可解得,那么它的解必须是有效可验证的。为什么?因为如果一个决策问题是可以有效地解决的,那就意味着我们可以有效地找到它的解决方案。然后,给出一个解决方案,我们可以简单地通过与问题的实际解决方案比较来验证它。换句话说,生成解决方案的算法的正确性自动证明了该解决方案。从这个结论可以看出,很明显,NP包含的问题子集也是有效可解的。这个子集被定义为P。
- P是所有可有效解决的决策问题的集合,是NP的一个子集。基本算法是多项式时间可解的。象棋决策问题不属于NP问题,因为没有一种有效的算法可以检查给定的棋盘是否有效。魔方决策问题属于NP问题,因为判断一个给定的魔方是否是一个解是很简单的。
哈密顿路径决策问题有一个有效的算法可以验证它的解,因此,它属于NP。有人可能会问这个问题是否在P中,一方面,我们不知道有一个有效的算法可以解决这个问题。另一方面,没有证据表明这样的算法不存在。事实上,这样的算法仍然有可能存在,而且还没有被发现。数独的决策问题也是一样,事实上,对于许多其他主要问题,包括布尔可满足性问题,旅行推销员问题,子集和问题,派系问题,图着色问题——尽管我们已经证明这些问题是NP,但没有证据表明他们在P 。这就是P=NP问题的意义所在:
P和NP真的是一样的吗?如果是的话,这就意味着NP中的所有问题都可以被有效地解决,尽管我们仍然没有找到实现这一点的神秘算法。否则,在NP中存在一些无法有效解决的问题,任何尝试解决将意味着浪费我们的时间和精力。
大多数时候,不能有效地解决问题是一件消极的事情。然而,在某些情况下,我们可以从问题的“硬度”中获益。属于NP而不属于P的问题,其主要特点是很难解决,但很容易验证其解决方案。
给定两个正整数n和k,判断n是否有一个质因数小于k。——质因数分解决策问题
由于该问题的解可以有效地验证,因此我们知道该问题属于NP,给定一个整数c,它需要“多项式时间”来知道c是否是一个比k小的质数,还是n的因数。但是,目前还没有一种算法可以在多项式时间内解决这一问题。因此,使用两个相当大的质数,就可以计算它们的乘法,这用于生成一个公钥和一个私钥。公钥可以为所有人所知,并用于加密消息。使用公钥加密的消息只能在合理的时间内使用私钥解密,假设没有有效的方法将一个大整数分解为它的质数因子。
- RSA-2048有617位十进制数字(2048位)。它是RSA数字中最大的,因式分解获得的现金奖金最高,为20万美元。除非在不久的将来在整数因子分解或计算能力方面取得重大进展,否则RSA-2048在许多年内可能无法分解。
但是,如果P=NP,则最后一个假设是错误的。为什么?如果P等于NP,那么质因数分解问题在P中,这意味着它可以被有效地解决。因此,一旦找到这样一个算法,任何公钥都可以在合理的时间内解密,而不需要私钥,这使得整个RSA密码系统完全崩溃,至少在理论上如此。
但是P=NP的负面影响与它所具有的潜在好处相比,是无关紧要的。在数学、优化、人工智能、生物学、物理学、经济学和工业领域中,确实存在着数以千计的NP问题,这些问题都是出于不同的需要而自然产生的,而有效的解决方案将使我们在许多方面受益。证明P=NP将意味着所有这些难题都可以在多项式时间内解决,这将导致在那些卓越的算法之后进行大规模的智力追求。一旦发现,这些算法将有可能推动人类的进步,远远超出我们的掌握。
- Christian Boehmer Anfinsen是1972年诺贝尔化学奖的获得者之一,因为他致力于研究一种小的,耐久的100个氨基酸长的蛋白质核糖核酸酶A的折叠。该蛋白质折叠问题是一个NP问题。
即使这样的结果,与解决NP问题的有效方法在数学本身引起的革命相比,也可能显得微不足道。
文章来源:《生物数学学报》 网址: http://www.swsxxb.cn/zonghexinwen/2020/1109/367.html
上一篇:谈祥柏其人与他的数学科普
下一篇:动物界里的数学家都有谁?