数学中的最著名的难题P=NP np是什么意思呢( 三 ) _知识经验

为什么？因为如果一个决策问题是可以有效地解决的，那就意味着我们可以有效地找到它的解决方案。
然后，给出一个解决方案，我们可以简单地通过与问题的实际解决方案比较来验证它。换句话说，生成解决方案的算法的正确性自动证明了该解决方案。
从这个结论可以看出，很明显，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的因数。
但是，目前还没有一种算法可以在多项式时间内解决这一问题。因此，使用两个相当大的质数，就可以计算它们的乘法，这用于生成一个公钥和一个私钥。
公钥可以为所有人所知，并用于加密消息。使用公钥加密的消息只能在合理的时间内使用私钥解密，假设没有有效的方法将一个大整数分解为它的质数因子。

数学中的最著名的难题P=NP np是什么意思呢( 三 )

猜你喜欢