什么是NP问题?

NP问题是给出一个建议的解决方案的问题,可以在多项式时间内验证该解决方案。例如,如果您有一个大学课程列表,并且需要创建一个时间表,以便课程不会发生冲突,那么这将是一个非常困难的任务(从复杂性的角度看)。然而, 鉴于 一个提议的时间表,您可以很容易地验证它的正确性。

加密领域的另一个重要例子是:给定一个数是两个非常大的素数相乘的结果,很难仅根据结果找到这些素数。然而, 鉴于 两个数字,很容易检查解决方案(相乘,比较)。

我特意选择了NP中而不是P中的例子(即很难找到解决方案的问题),这样你就可以理解其中的区别。所有容易解决的问题,也容易验证-只需解决和比较。也就是说,p是np的一个子集。

这不是一个真正的答案,因为Piccolo的链接更有用,但是一位惠普研究人员声称已经证明了P!=np,这是纸。

www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

它还没有被接受,但我祝他100万美元好运。