P与NP问题澄清

Question

引用自维基百科，关于算法时间复杂度的P与NP问题，它“...询问了一个问题，即是否每个能够被计算机快速验证其解的问题也能够被计算机快速求解。”

我希望有人可以澄清这里“验证问题”和“解决问题”的区别。

- kjh

---

我也不理解这个问题。如果你要验证一个答案，难道不是必须先解决它才能进行比较吗？ - Luke Taylor

@LukeTaylor 将某物与正确解决方案（或正确解决方案集）进行比较并不是验证答案的唯一方法，特别是对于具有无限解的问题。例如，考虑一个方程 - 或者甚至是一个不等式，更容易选择一个可能的解并评估它以查看该可能的解是否满足方程，而不是首先解决方程。 - Theraot

Answer 1

我希望有人能够澄清这里“验证问题”和“解决问题”的区别。

这里不是“验证问题”，而是“验证解决方案”。例如，您可以在多项式时间内检查给定集合是否对SAT有效。生成这样的集合实际上是NP困难的。维基百科文章NP（复杂性）中的{{link2：基于验证器的定义部分}}可能会对您有所帮助：

基于验证器的定义

为了解释NP的基于验证器的定义，让我们考虑子集和问题：假设我们有一些整数，比如{-7，-3，-2，5，8}，我们想知道是否有一些这些整数相加等于零。在这个例子中，答案是“是”，因为整数的子集{-3，-2，5}对应于和(-3) + (-2) + 5 = 0。决定是否存在这样一个和为零的子集的任务被称为子集和问题。

随着我们输入算法的整数数量变得越来越多，子集的数量呈指数级增长，实际上子集和问题是NP-完全的。然而，请注意，如果我们给出一个特定的子集（通常称为证书），我们可以轻松地检查或验证子集和是否为零，只需将子集的整数相加即可。因此，如果和确实为零，那个特定的子集就是答案为“是”的证明或证人。验证给定子集是否具有零和的算法称为验证器。如果一个问题存在一个在多项式时间内执行的验证器，则该问题被称为NP问题。在子集和问题的情况下，验证器仅需要多项式时间，因此子集和问题属于NP。

如果您更喜欢图论，Hamilton cycle是一个NP完全问题。检查给定解是否为汉密尔顿回路很容易（线性复杂度，遍历解路径），但如果P != NP，则不存在具有多项式运行时间的算法来解决该问题。

也许在这种情况下，“快速”这个术语是误导性的。仅当算法的最坏运行时间受多项式函数限制时，例如O(n)或O(n log n)，算法才在这方面快速。对于给定长度为n的范围内的所有排列的创建是没有限制的，因为您有n!不同的排列。这意味着问题可以在n ¹⁰⁰ log n中解决，这需要很长时间，但仍被认为是快速的。另一方面，TSP的第一个算法是O(n!)，另一个算法是O(n² 2ⁿ)。与多项式函数相比，这些东西增长得非常快。

- Zeta

---

LOL，“验证问题”很有趣。 - user541686

@Mehrdad：实际上有时候很难向别人解释存在的问题：“你说什么，你没去杂货店？”-“我试图计算哈密顿回路以便恰好只看到每个角落一次，但我的程序仍在运行”-“这太荒谬了！”-“不，它是NP完全问题。” - Zeta

Answer 2

RSA加密使用质数，如下所示：两个大质数P和Q（每个数字200-400位）相乘形成公钥N。N=P*Q为了破解加密，需要找出给定N的P和Q。虽然找到P和Q非常困难，可能需要数年时间，但验证解决方案只需将P乘以Q并与N进行比较。因此，解决问题非常困难，而验证解决方案则不需要任何东西。

附注：本例仅为简化此问题的RSA的一部分。真正的RSA更加复杂。

- Davit Yeghiazaryan

---

虽然我们已经知道了数乘的多项式时间算法已有千年历史（并且已经有几十年的时间可以进行次二次方级别的计算），但是不知道如何快速因式分解只能证明我们的无知（如果这种无知是被共享的话）。 - greybeard