algorithm - 有没有可以在多项式时间内得到答案的 NP 例子？

Question

我刚刚在维基百科上阅读了 NP 和 P，我有两个问题：

1. 我们可以在多项式时间内求解一个 NP 示例吗？
2. 有没有可以在多项式时间内得到答案的 NP 例子？</li>

Answer 1

免责声明：此答案侧重于处理存在多项式时间算法未知的问题这一事实的实际方面。为了从理论的角度给出准确的答案，问题中使用的术语不够清楚。

计算机科学中 NP 的两个含义很容易混淆。

(1) NP 作为一类 NP 完全问题：

对于这些问题，目前都没有找到多项式算法。已经证明，如果为这些问题之一找到这样的算法，则可以在多项式时间内解决每个问题。NP 完整性的标准示例是旅行商问题。

(2) NP 作为需要指数时间的算法的属性：

任何 NP 算法都可以解决小尺寸 N。问题只是计算次数随 N 呈指数增长（即非常快）。

有些问题最初只知道 NP 算法，但后来发现了多项式时间算法。不幸的是，我现在无法举出一个例子。

对于许多只有 NP 解决方案的问题，存在多项式时间算法，可以产生最佳解决方案的良好近似值。对于许多应用程序来说，这已经足够了。