问题标签 [p-np]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
computer-science - 什么是“P=NP？”，为什么它是一个如此著名的问题？
P=NP 是否是计算机科学中最著名的问题。这是什么意思？为什么它如此有趣？
哦，为了获得额外的荣誉，请张贴一份声明的真假证明。:)
algorithm - 假设 P=NP 证明会是什么样子？
它是针对特定 NP 完全问题的多项式时间算法，还是只是证明存在 NP 完全问题解决方案的抽象推理？
似乎特定的算法更有帮助。有了它，我们要多项式解决一个 NP 问题，我们要做的就是将其转换为证明有解决方案的特定 NP 完全问题，我们就完成了。
p-np - 这个 P != NP 证明缺少什么？
我试图找回密码。想到这一点，我意识到“密码恢复”问题是 NP 问题的一个很好的例子。如果您知道密码，则很容易在多项式时间内对其进行验证。但是，如果您不知道密码，则必须搜索可能的解决方案的整个空间，这可能会花费指数级时间。
现在我的问题是：这是否表明 P != NP 因为“密码恢复”是 NP 的一个元素，可以证明它需要多于多项式时间才能运行？
computer-science - P=NP：最有前途的方法是什么？
我知道 P=NP 到现在还没有解决，但是任何人都可以告诉我以下内容：目前最有希望的数学/计算机科学方法可以帮助解决这个问题吗？或者，到目前为止，甚至没有任何已知的可能有用的方法吗？有没有关于这个主题的（免费）纲要，我可以在其中找到在该领域完成的所有/大部分研究？
math - 解释 Vinay Deolalikar 证明 P != NP
最近，HP 实验室的 Vinay Deolalikar 发表了一篇论文，声称证明了P != NP。
有人能解释一下这个证明如何适用于我们不太喜欢数学的人吗？
complexity-theory - 什么是NP问题？
我阅读了维基百科上的文章，但无法理解 NP 问题到底是什么。谁能告诉我关于它们以及它们与 P 问题的关系是什么？
computer-science - 为什么这样称呼 NP 问题（以及 NP-hard 和 NP-complete）？
真的.. 我将在本周二进行最后一次毕业考试，这是我永远无法理解的事情之一。我意识到可以在多项式时间内验证 NP 问题的解决方案。但决定论与此有什么关系呢？
如果你能解释一下 NP-complete 和 NP-hard 的名字是从哪里得到的，那就太好了（我很确定我明白了它们的含义，我只是不明白它们的名字与它们的含义有什么关系是）。
对不起，如果那是微不足道的，我似乎无法理解（-：
谢谢大家！
computer-science - 不是 NP-complete 的 NP-hard 问题更难？
据我了解，所有 NP 完全问题都是 NP 难题，但已知一些 NP 难题不是 NP 完全问题，并且 NP 难题至少与 NP 完全问题一样难。
这是否意味着不是 NP 完全的 NP 难题更难？以及如何更难？
algorithm - 某些排序可以是 P、NP 和 NP-Complete 吗？
我很困惑，这是我阅读后的想法：
P 在 NP 中，而 NP 在 NP-Complete 中。因此，所有 P 都可能是 NP 和 NP-Complete？
这是否意味着存在可能是 NP 和 NP-Complete 的排序算法？
希望这听起来不会太愚蠢。