算法分析 - 是否有任何算法具有 n^99 数量级的最佳情况复杂度？

Question

是否有任何算法具有 n^99 数量级的最佳情况复杂度？这个NP完整吗？如果不是，我们如何分析此类算法？

Answer 1

您必须谨慎对待这个问题的措辞。只有问题可以是NP-complete，而不是算法，所以即使我可以为问题设计一个最有效的算法并且在时间 Θ(n⁹⁹) 中运行，算法 不会NP-complete。

对于 NP-complete 的问题，它必须是一个决策问题，一个接受一些输入并输出"is"或“不。”所以你可以问下面的问题:有没有不能在小于Θ(n⁹⁹)的时间内解决的决策问题，如果有，这样的问题是不是NP -完成了吗？

有一个名为 time hierarchy theorem 的结果也就是说，对于大多数表现良好的函数，存在可以在该时间内解决的决策问题，但不会少于它。特别地，我们可以构造一个可以在时间 Θ(n⁹⁹) 内解决但不能在时间 O(n⁹⁹/log n) 内解决的决策问题，例如。据我所知，我们不知道任何决策问题的最有效可能算法的运行时间正好 Θ(n⁹⁹)，尽管如您所见我们可以非常接近!

那么这些问题NP是否完备？好吧，我们不知道!此属性的任何问题都属于 P 类。如果 P = NP，那么它最终会是 NP - 完全不是因为 n^{99< 有什么特别之处/sup> 但因为P 中的每个 问题都是NP-完全的。* 另一方面，如果P> ≠ NP，那么这个问题就不可能是NP-完全的，因为没有NP-完全的问题属于P>。同样，这里关于 n99 没有什么特别之处，只是它是一个多项式。}

* 从技术上讲，这两个微不足道的问题(“给定一个输入，是 0 = 0 吗？”和“给定一个输入，是 0 = 1 吗？”)不会是NP-如果 P = NP 则完成。