什么是NP问题？

Question

我阅读了有关Wikipedia的文章，但不了解NP问题到底是什么。谁能告诉我有关它们的信息，以及它们与P问题有什么关系？

Answer 1

NP问题是给定解决方案的问题，您可以在多项式时间内验证解决方案。例如，如果您有大学课程列表，并且需要创建时间表以使课程不会发生冲突，那么这将是一项非常困难的任务（在复杂性方面）。然而， 给出 提议的时间表，您可以轻松验证其正确性。

加密字段中的另一个重要示例：给定一个数字是乘以两个非常大的素数的结果，很难仅根据结果找到这些素数。然而， 给出 两个数字，很容易检查解决方案（乘以它们，比较）。

我有意选择了NP中的示例，而不是在P中（即难以找到解决方案的问题），因此您可以理解差异。所有易于解决的问题，也很容易验证 - 只需解决和比较即可。也就是说，p是NP的子集。

Answer 2

并不是真正的答案，因为Piccolo的链接更有用，但是HP研究人员声称已经证明P！= NP，这是论文。

www.hpl.hp.com/personal/vinay_deolalikar/papers/pnp12pt.pdf

它尚未接受，但我祝他100万美元好运。