algorithm - P 与 NP 澄清

Question

引用自维基百科的 P vs NP 问题，关于算法的时间复杂度“......询问是否每个问题的解决方案都可以通过计算机快速验证，也可以通过计算机快速解决。”

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

Answer 1

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

不是“验证问题”，而是“验证解决方案”。例如，您可以在多项式时间内检查给定集合是否对SAT有效。这种集合的实际生成是 NP 困难的。Wikipedia 文章 NP (complexity) 中基于验证器的定义部分可以为您提供一些帮助：

基于验证者的定义

为了解释NP的基于验证者的定义，让我们考虑子集和问题：假设给定一些整数，例如 {−7, −3, −2, 5, 8}，我们希望知道这些整数中的一些是否总和为零。在这个例子中，答案是“是”，因为整数子集 {−3, −2, 5} 对应于和 (−3) + (−2) + 5 = 0。存在总和为零的子集称为子集和问题。

随着我们输入算法的整数数量变大，子集的数量呈指数增长，实际上子集和问题是NP 完全的。但是，请注意，如果给定一个特定的子集（通常称为证书），我们可以轻松地检查或验证子集总和是否为零，只需将子集的整数相加即可。因此，如果总和确实为零，则该特定子集就是答案为“是”这一事实的证据或见证。验证给定子集的和是否为零的算法称为验证器。据说问题出在NP中当且仅当存在一个在多项式时间内执行的问题的验证器。在子集和问题的情况下，验证者只需要多项式时间，因此子集和问题在NP中。

如果您更喜欢图论，那么汉密尔顿循环是一个 NP 完全问题。检查给定的解决方案是否是汉密尔顿循环（线性复杂度，遍历解决方案路径）是微不足道的，但如果 P != NP 则不存在解决问题的多项式运行时算法。

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

Answer 2

RSA 加密使用如下素数：将两个大素数 P 和 Q（每个 200-400 位）相乘以形成公钥 N。N=P*Q 要破解加密，需要在给定 N 的情况下计算出 P 和 Q。 P 和 Q 非常困难，可能需要数年时间，验证解决方案只是将 P 乘以 Q 并与 N 进行比较。因此解决问题非常困难，而验证解决方案不需要任何时间。

PS 该示例只是针对此问题简化的 RSA 的一部分。真正的 RSA 要复杂得多。