P!= NP问题

Question

这不是一个"纯粹的"编程问题,但由于它深入参与编程理论,我认为最好在这里问一下.

关于P NP问题,摘自http://en.wikipedia.org/wiki/P_versus_NP_problem:"实质上,问题P = NP？问:假设可以快速验证是或否问题的答案.那么,答案本身也可以快速计算出来吗？"

我想知道,验证答案的速度与生成解决方案的速度有什么关系？

Answer 1

假设你有很大的并行性 - 无论你想要多少.然后,您可以同时生成所有可能的解决方案,检查哪些是正确的,并输出正确的解决方案.在存在无限并行性的情况下,这是一种生成解的方法.NP中的一组问题是这个程序可以快速运行的问题,因为它执行的唯一有趣的计算步骤是检查解决方案是否正确,这可以有效地解决NP中的问题.请注意,对于其他一些问题,即使这种并行性也不允许我们快速找到解决方案,因为它要求检查解决方案很容易.

但我们没有无限的并行性.我们能以某种方式模拟它,只有多项式的开销吗？如果是这样,我们可以想象运行上述过程,并有效地为每个问题找到解决方案,以便进行验证.这是P vs. NP问题.

直观地,似乎很清楚答案是"不"(即P!= NP).我们怎么可能模拟无限的并行性？几乎每个专家都相信这一点.但如何证明它是一个谜,一个价值100万美元的奖金.

Answer 2

本质上，在一组 NP（非确定性多项式时间）问题中，可以在多项式时间内验证答案。问题是是否所有此类问题都可以在多项式时间内确定。

如果P=NP成立，并且这样的算法被发现，许多难以解决但易于验证解决方案的问题，例如证明，变得像验证一样容易解决。