为什么多项式时间称为“高效”？

Question

为什么在计算机科学中，最多多项式的任何复杂性被认为是有效的？

对于任何实际应用^（一个）, ，具有复杂性的算法$ n^{ log n} $比及时运行的算法快，例如$ n^{80} $，但是在后者有效的时候，第一个被认为是效率低下的。逻辑在哪里？

^{（a）假设宇宙中的原子数约为$ 10^{80} $。}

Answer 1

关于“效率”的另一个观点是，多项式时间使我们能够定义不取决于机器模型的“效率”概念。具体而言，教会繁琐的论文的一种称为“有效的教会论文”，该论文说，在类型的机器模型上在多项式时间内运行的任何问题也将在另一个同样强大的机器模型上在多项式时间内运行。

这是对一般CT论文的较弱陈述，并且被随机算法和量子算法违反了某种“有点”，但在能够通过更改Poly解决NP-HARD问题的意义上没有违反。机器型号。

这最终是多项式时间是理论中流行概念的原因。但是，大多数人意识到这并不能反映“实际效率”。有关此的更多信息，Dick Lipton关于'银河算法'是一本很棒的读物。

Answer 2

从理论上讲，我们关心渐近行为，并根据其渐近行为来描述问题和算法类别。这里的关键字是 渐近学. 。 $ o（n^{80}）$比$ o（n^{ log n}）$渐变，即，从$ n> 1208925819614614629174706176 $开始恒定系数，没有低阶项。

但是，实际上，注意指数和恒定系数都引起了人们的注意。在实践中，输入尺寸不能增长到七十亿，因此，对于所有目的而言，$ n^{ log n} $将是$ n^{80} $的优越选择。其他因素在实践中也很重要：并行性，内存访问模式（例如局部性）。

例如，大多数用于整数乘法的库，例如 GMP 将实施算法的混合物，并 根据输入大小选择下等算法 尽管这些算法可能渐近较低，但根据输入大小选择实际上的算法。某些渐近的“下等”算法将在某些输入大小上更快，并且将通过最佳算法选择。

另一个示例，已知最快的矩阵乘法算法是 Coppersmith-Winograd算法 以$ o（n^{2.3737}）$运行（最近有改进； 这里还有更多）。但是，它从未实施，因为（1）很难（2）恒定系数是巨大的。所有线性代数软件包的最佳选择 Strassen.

TL; DR理论关心渐近行为，以比较算法，因为输入大小的极限是任意数量的。

Answer 3

这个答案将查看您问题的“更大图景”上下文。计算机科学实际上是一门相对年轻的，有点开放的科学，它对一些基本和基本问题还没有很好的答案。基本问题“有效计算的是什么”是 准确 或者 大致 在CS中正式（取决于意见）为著名的PS VS NP问题（或密切相关的P与Exptime问题），它仍然 打开 经过十多年的最初是由库克/列文（Cook/Levin）〜170引入的，以及世界上最伟大的计算机科学家的剧烈工作（许多数学家也对这个问题作为基本问题感兴趣）。

换句话说，即使有一个 粗糙的 定义“高效”为P时间，也是有价值的科学奖项之一 - 即10年以上问题附带的100万美元奖励 - 计算机科学甚至无法证明某些问题（接近此边界）必须或不得不有效（PTIME）算法。因此，“高效”的确切定义比P时间更精确，甚至不需要 可能的 此时。如果/当p vs np猜想以一种或另一种方式解决时，可能会或可能是更严格的“有效”定义。

此外，人们可能会觉得对“高效”的PTIME定义甚至可能有点“草率”，大多数计算机科学家可能会同意，几乎所有人都认为P VS NP猜想是解决，解决，解决，他们甚至可能认为这种断言或观察是微不足道的观点...换句话说，可以这么说 它正在进行中 /我们正在努力. 。 （实际上，主流的计算机科学家甚至在一半开玩笑的范围内，通常将差距和缺乏进度/确定的分离称为 尴尬.)

实际上，甚至有密切相关的/明显更强 猜想比p vs np，即np vs p/poly，目前也无法通过计算机科学解决。它猜想NP时间问题无法通过 任何 “ P大小”电路，即甚至不限于算法/图灵机可以创建的电路。

至于p和np可能有多硬 - 有一些充分的理由认为这可能是 至少很难 作为数学中非常古老的Riemann猜想（现在为1.5 世纪 旧），因为十年来两者都获得了相同的100万美元奖励，而且两者都没有得到解决。

因此，换句话说，要精确定义哪些算法真正“有效”实际上是其中之一 理论科学和数学中最重要，最困难的现有开放问题.

实际上，“什么有效计算”的问题实际上更加微妙，因为教会培养论文的一种称为p时间ct论文，尚不清楚量子计算是否实际上是否存在 违反 它。随着p时间QM的突破性的突破，这项研究中考虑了巨大的转折。换句话说，实际上有效计算的问题实际上可以一直延伸到深层物理原理，并与量子计算相比是否比经典计算更有效地计算，这在理论CS和高级物理学中也是一个普遍开放的问题。

因此，甚至可以补充说，P和NP和有效计算的问题可能至关重要或至关重要 - 除了CS和数学外， 物理.

[1] P与NP问题，Wikipedia

[2] 千年奖问题

[3] P/Poly类，Wikipedia

[4] Shor的算法

Answer 4

多项式时间算法仅与最困难的非多项式时间相比，尤其是所谓的NP完整时间，才被认为是有效的。请参阅图像： P，NP，NP完整和NP - 硬性问题的Euler图.