最佳情况运行时解决NP-Complete问题？

Question

什么是解决特定NP-Complete问题时最快的算法？例如,旅行推销员的朴素实现是O(n!),但是通过动态编程,它可以在O(n ^ 2*2 ^ n)中完成.是否有任何"更容易"的NP-Complete问题具有更好的运行时间？

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

Answer 1

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

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

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