什么是NP问题？
我读了维基百科上的文章，但无法理解 NP 问题到底是什么。谁能告诉我它们以及它们与 P 问题的关系是什么？
I read the article on wikipedia but could not understand what exactly are NP problems. Can anyone tell me about them and also what is relation of them with P Problems?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
NP问题是给定一个建议的解决方案，可以在多项式时间内验证该解决方案的问题。例如，如果您有一份大学课程列表，并且需要创建一个时间表以便课程不会发生冲突，那么这将是一项非常困难的任务（复杂性方面）。但是，给定一个建议的时间表，您可以轻松验证其正确性。
加密领域的另一个重要例子：给定一个数字，它是两个非常大的素数相乘的结果，仅根据结果很难找到这些素数。然而，给定两个数字，很容易检查解决方案（将它们相乘，比较）。
我特意选择了 NP 中的例子而不是 P 中的例子（即很难找到解决方案的问题），这样你就可以理解其中的区别。所有容易解决的问题也都容易验证——只需解决和比较即可。也就是说，P 是 NP 的子集。
NP problems are problems that given a proposed solution, you can verify the solution in a polynomial time. For example, if you have a list of University courses and need to create a schedule so that courses won't conflict, it would be a really difficult task (complexity-wise). However, given a proposed schedule, you can easily verify its correctness.
Another important example from the field of encryption: given a number which is the result of multiplying two very large prime numbers, it's very difficult to find those primes based only on the result. However, given two numbers, it's very easy to check the solution (multiply them, compare).
I have intentionally chose examples that are in NP and not in P (i.e. problem that are hard to find the solution for) so you can understand the difference. All problems that are easy to solve, are also easy to verify - just solve and compare. That is, P is a subset of NP.
这并不是一个真正的答案，因为 Piccolo 的链接更有用，但惠普研究人员声称已经证明了 P != NP，这是论文。
www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt。 pdf
尚未被接受，但我祝他好运，获得 100 万美元。
Not really an answer, because Piccolo's link is more useful, but a HP researcher claims having proven P != NP, here is the paper.
www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
It was not accepted yet, but I wish him good luck for the 1M$.