算法分析 - 是否有任何算法具有 n^99 数量级的最佳情况复杂度？
Algorithmic Analysis - Are there any algorithms having their best case complexity of the order of n^99?
是否有任何算法的最佳情况复杂度为 n^99 数量级？这个NP完整吗？如果不是，我们如何分析这样的算法？
Are there any algorithms having their best case complexity of the order of n^99?
考虑以下算法：
- 读取输入，跟踪其长度n。
- 发出长度为 n99.
的输出
（好吧，这不是一个非常精确的描述，但你明白了。只需执行 99 个嵌套循环，所有循环都遍历输入，并让最内层的循环打印 x 或其他内容。）
Is this NP complete?
这相当于提问，"Does P = NP?"。如果你能找到答案，你就会出名。 :-)
根据定义，复杂度为N^99的算法是多项式时间，在P中也是如此。如果你能找到一个NP完全的算法，你就证明了P=NP，所以我认为是你不太可能找到一个 NP 完全的。
P vs NP 如此有趣的原因之一是，在实践中，我们自然遇到的 P 中的算法往往具有比 99 小得多的幂。然而，有一些方法可以构建几乎任意复杂度的非常人工的算法, 所以肯定有复杂度 N^99 的算法。 （参见例如 https://en.wikipedia.org/wiki/Time_hierarchy_theorem 或观察特定大小的电路数量比不同布尔函数的数量增长得更慢，因此必须有一些函数没有特定大小的电路）
FWIW Donald Knuth 认为 P=NP，但很难找到指数非常大的算法。参见例如http://www.informit.com/articles/article.aspx?p=2213858 中的问题 17。这与具有更大指数的更复杂算法并不矛盾：这些算法会做其他事情（事实上，它们可能非常人为）。
你必须谨慎对待这个问题的措辞。只有 problems 可以 NP-complete，而不是 algorithms，所以即使我可以设计一个算法一个最有效的问题，运行 时间 Θ(n99)，算法 不会是 NP-完成.
要使问题 NP 完整，它必须是一个 决策问题，一个接受一些输入的问题并输出 "yes" 或 "no." 所以你可以问以下问题：是否有任何决策问题不能在小于 Θ(n99) 的时间内解决, 如果是这样，这样的问题 NP-complete?
有一个名为 time hierarchy theorem 的结果表明，对于大多数 well-behaved 功能，有些决策问题可以在该时间内解决，但不会少于它。特别地，我们可以构造一个可以在时间 Θ(n99) 内解决但不能在时间 O(n99[=57=) 内解决的决策问题] / log n)，例如。据我所知，我们不知道任何决策问题的最有效可能算法及时运行 exactly Θ(n99)，尽管如您所见，我们可以非常接近！
那么这些问题 NP 是否完整？好吧，我们不知道！ 属性 的任何问题都属于 class P。如果 P = NP，那么它最终会是 NP-complete 不是因为有n99 有一些特别之处，但是因为 每个 P 中的问题都是 NP-complete.* 另一方面，如果P ≠ NP，那么这个问题不可能是NP -complete 因为没有 NP-complete 问题属于 P。同样，这里关于 n99 除了它是一个多项式之外没有什么特别的。
* 从技术上讲，两个 微不足道的问题 （"given an input, is 0 = 0?" 和 "given an input, is 0 = 1?"）不会是 NP-如果 P = NP.
则完成
其中一个问题是 k-clique 问题。
Given a graph of size n, is there any clique with k vertices? (k is considered a constant).
一个明显的 brute-force 算法检查图顶点的所有 k-子集并测试它们是否是一个团。因为有 (nk) k-子集, 并且每一个都可以在(k2) 时间内被检出, 总复杂度变为(nkk2) 或者只是 (nk)（因为k是常数）。
这个问题的渐近最著名的算法（虽然完全不切实际）运行在 (n0.792k).
通过改变 k，可以处理任何所需的复杂性。
是否有任何算法的最佳情况复杂度为 n^99 数量级？这个NP完整吗？如果不是，我们如何分析这样的算法？
Are there any algorithms having their best case complexity of the order of n^99?
考虑以下算法：
- 读取输入，跟踪其长度n。
- 发出长度为 n99. 的输出
（好吧，这不是一个非常精确的描述，但你明白了。只需执行 99 个嵌套循环，所有循环都遍历输入，并让最内层的循环打印 x 或其他内容。）
Is this NP complete?
这相当于提问，"Does P = NP?"。如果你能找到答案，你就会出名。 :-)
根据定义，复杂度为N^99的算法是多项式时间，在P中也是如此。如果你能找到一个NP完全的算法，你就证明了P=NP，所以我认为是你不太可能找到一个 NP 完全的。
P vs NP 如此有趣的原因之一是，在实践中，我们自然遇到的 P 中的算法往往具有比 99 小得多的幂。然而，有一些方法可以构建几乎任意复杂度的非常人工的算法, 所以肯定有复杂度 N^99 的算法。 （参见例如 https://en.wikipedia.org/wiki/Time_hierarchy_theorem 或观察特定大小的电路数量比不同布尔函数的数量增长得更慢，因此必须有一些函数没有特定大小的电路）
FWIW Donald Knuth 认为 P=NP，但很难找到指数非常大的算法。参见例如http://www.informit.com/articles/article.aspx?p=2213858 中的问题 17。这与具有更大指数的更复杂算法并不矛盾：这些算法会做其他事情（事实上，它们可能非常人为）。
你必须谨慎对待这个问题的措辞。只有 problems 可以 NP-complete，而不是 algorithms，所以即使我可以设计一个算法一个最有效的问题，运行 时间 Θ(n99)，算法 不会是 NP-完成.
要使问题 NP 完整，它必须是一个 决策问题，一个接受一些输入的问题并输出 "yes" 或 "no." 所以你可以问以下问题：是否有任何决策问题不能在小于 Θ(n99) 的时间内解决, 如果是这样，这样的问题 NP-complete?
有一个名为 time hierarchy theorem 的结果表明，对于大多数 well-behaved 功能，有些决策问题可以在该时间内解决，但不会少于它。特别地，我们可以构造一个可以在时间 Θ(n99) 内解决但不能在时间 O(n99[=57=) 内解决的决策问题] / log n)，例如。据我所知，我们不知道任何决策问题的最有效可能算法及时运行 exactly Θ(n99)，尽管如您所见，我们可以非常接近！
那么这些问题 NP 是否完整？好吧，我们不知道！ 属性 的任何问题都属于 class P。如果 P = NP，那么它最终会是 NP-complete 不是因为有n99 有一些特别之处，但是因为 每个 P 中的问题都是 NP-complete.* 另一方面，如果P ≠ NP，那么这个问题不可能是NP -complete 因为没有 NP-complete 问题属于 P。同样，这里关于 n99 除了它是一个多项式之外没有什么特别的。
* 从技术上讲，两个 微不足道的问题 （"given an input, is 0 = 0?" 和 "given an input, is 0 = 1?"）不会是 NP-如果 P = NP.
则完成其中一个问题是 k-clique 问题。
Given a graph of size n, is there any clique with k vertices? (k is considered a constant).
一个明显的 brute-force 算法检查图顶点的所有 k-子集并测试它们是否是一个团。因为有 (nk) k-子集, 并且每一个都可以在(k2) 时间内被检出, 总复杂度变为(nkk2) 或者只是 (nk)（因为k是常数）。
这个问题的渐近最著名的算法（虽然完全不切实际）运行在 (n0.792k).
通过改变 k，可以处理任何所需的复杂性。