language-agnostic - 解决 NP 完全问题的最佳情况运行时间？

Question

解决特定 NP 完全问题的最快算法是什么？例如，旅行推销员的简单实现是 O(n!)，但使用动态规划可以在 O(n^2 * 2^n) 中完成。是否有任何可能“更简单”的 NP-Complete 问题具有更好的运行时间？

我对确切的解决方案而不是近似值感到好奇。

Answer 1

NP-Complete 问题的一个特点是 NP 中的任何问题都可以在最多多项式时间内机械​​地转换为任何 NP-Complete 问题。

因此，无论任何给定 NP 完全问题的最佳解决方案是什么，对于任何其他 NP 问题，它都会自动成为类似的好解决方案。

鉴于动态规划可以在 2^n 时间和 2^n 空间内解决旅行商问题，所有其他 NP 问题也必须如此[好吧，加上应用转换的时间，我猜 - 所以它可能是 2^ (n+1)]。

Answer 2

[...] 使用动态编程可以在 O(n^2 * 2^n) 中完成。是否有任何可能“更简单”的 NP-Complete 问题具有更好的运行时间？

有点。您可以通过创建一个人为的问题来摆脱任何多项式因素，该问题在多项式更大的输入中编码相同的解决方案。只要输入只是多项式更大，由此产生的问题仍然是 NP 完全的。由于复杂性是根据定义将输入大小映射到运行时间的函数，如果输入大小增长，该函数将进入较低的 O 类。

因此，在 TSP 上运行相同的算法，输入用 n^2 无用位填充，复杂度为 O(1 * 2^sqrt(n))。

Answer 3

通常，如果不尝试所有组合（可能存在负距离等），您将无法找到通用旅行商问题的最佳解决方案。

通过添加额外的限制并放宽获得最佳解决方案的要求，您可以大大加快速度。

For instance you can get polynomial executable time if the distances in the problem obey the "it is not longer to go directly from A to B than going from A to C to B" (i.e. a shortcut is never longer), and you can live with the result maximally being 1.5 times the optimal value. See http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP