complexity-theory - 什么是NP问题？

Question

我阅读了维基百科上的文章，但无法理解 NP 问题到底是什么。谁能告诉我关于它们以及它们与 P 问题的关系是什么？

score 8 · Accepted Answer

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

加密领域的另一个重要例子：给定一个数字，它是两个非常大的素数相乘的结果，仅根据结果很难找到这些素数。但是，给定两个数字，很容易检查解决方案（将它们相乘，比较）。

我特意选择了 NP 中而不是 P 中的示例（即难以找到解决方案的问题），以便您了解其中的区别。所有容易解决的问题也很容易验证 - 只需解决和比较即可。也就是说，P 是 NP 的子集。

score 0 · Accepted Answer

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

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

2 回答 2