为什么大多数科学家认为p≠np？

Question

我读到大多数科学家不认为p = np。它可能是主观的，但是您可以简化为什么不呢？我没有足够的消息来发表意见，但是我想知道定义和一些“非常简单”的解释，为什么要相信一种或另一种情况，例如为什么甚至相信它可以证明它？

Answer 1

NP完整问题可以转换为另一个NP完整问题。实际上，有很多已知的NP完整问题，甚至可以说任何真正有趣的问题都是NP完整的。因此，如果您知道一种解决方法 任何 np-complete问题$ x $迅速，您可以采用其他任何NP完整问题，将其转换为$ x $的实例，并也很快解决。

一些精明的研究花了很多时间来研究这些困难问题。尽管有很多努力和几年，我们仍然没有任何NP完整问题的多项式时间算法。我们还具有“如果您可以更快/更好地执行此操作，则P = NP”的有条件结果。

至于证明这一主张，我们也许不确定。我们所知道的是，无论证明外观如何，它都不是某种类型的。因此，至少有证据表明，它将必须解决如何避免一些已知困难。

有关更多详细信息，您可以首先看一下Sipser的书，然后看看Arora-Barak的书。

Answer 2

p≠np似乎是一种“计算速度限制”或“无免费午餐定理”或“基本瓶颈”，其中许多其他类似的科学，数学甚至物理学分支。在所有已知算法中，解决SAT问题所需的计算量都是指数的，并且多年来，高级研究人员发明了许多计算。数十年的研究已经独自解决了SAT，实际上是超过½世纪的研究，例如 戴维斯·普特南算法 在1960年的NP完整性理论之前，在1960年的大约十年中都被发现并进行了分析。

直观地p≠np指出，无论算法设计师有多么出色的创造力，都在提高代码效率方面都有基本的限制。这样，它甚至与物理定律相似，例如热力学。它可以解释为对每次可以完成的信息处理量的限制 任何 物理系统。

但是，没有人认为定理是真实的“非常简单”的原因，至少在证明结构意义上，因为如果存在这种原因，似乎现在可以发现它。换句话说，这似乎是正确的，但原因是“极其复杂”。可能来自几十年的未来研究和分析/简化 后 事实证明，它可能开始在20-20的事后看待/回顾中看起来“简单”，某些证据随着时间的流逝，尤其是关键的证据。

关于此的另一个角度是，现代密码学是基于“硬”函数和“陷阱门”函数的存在，其中计算以一种方式而不是另一种方式很容易。换句话说，研究人员对这样的信念非常有信心，他们认为他们已经基于前提建立了精心设计的密码系统。

但是，少数研究人员“不排除” p = np，其中一些有成就的专家，例如 RJ Lipton.

这些帖子的原因之一是，我相信我们认为作为P $ stackrel {？} {=} $ np的社区中的大部分内容可能是最好的猜测，而最坏的情况是完全错误的。大多数人认为“显然” p≠np，但我不太确定。我真的认为相反的情况也是如此。

看到Gasarch的这些不错的民意调查

[1] Gasarch P与NP民意调查I，2002年

[2] Gasarch P与NP民意调查II，2012年

至于其固有的可预订性，就该主题进行了一些严肃的专家辩论。请参阅此参考/调查，以及著名的屡获殊荣的论文。

[3] p≠np是正式独立的吗？ 亚伦森

[4] 自然证明 拉兹博罗夫/鲁迪奇

Answer 3

我认为人们总是相信具有“更多量词”的猜想。我们总是猜想“没有数字”，而不是“有一个数字”或“有无限的这样的数字”，而不是“没有比这更大的数字”。原因之一应该是我们认为，如果有这样的数字/绑定，那么我们可以找到它/猜测。

使用p = np，如果您认为它们是平等的，那么您应该认为SAT有一种算法，再次是建设性的东西，如果我们无法显示出该算法，我们猜想它没有。至少在很多聪明的人努力工作并找不到它之后。

请注意，p = np与数字理论猜想不同，这些猜想是基于一些经验证据的，例如假设素数像随机数一样。这里没有支持假设，除了到目前为止，没有人能找到算法。我想这会使猜想“较小的可能性”，但是当然，没有正式的方法将概率分配给数学语句。

但是可能您最好阅读专家的意见，请参阅此处：http://en.wikipedia.org/wiki/p_versus_np_problemumblemumblemumblemblembort #to_to_believe_p_.e2.89.a0_np