P != NP问题

Question

这不是一个“纯粹”的编程问题，但因为它与编程理论有很深的关系，所以我认为最好在这里提问。

关于P NP问题，摘自http://en.wikipedia.org/wiki/P_versus_NP_problem：“本质上，问题P= NP?问:假设一个是或否问题的yes答案可以快速验证。那么，答案本身也可以快速计算出来吗？”

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

Answer 1

本质上，在NP或非确定性多项式时间问题的集合中，答案可以在多项式时间内得到验证。问题是，是否所有这样的问题都可以在多项式时间内被确定。

如果P=NP为真，并且发现了这样的算法，那么许多难以解决但易于验证的问题，例如证明，就变得像验证一样容易解决。

Answer 2

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

但是我们没有无限的并行性。我们能以某种方式模拟它，只需多项式的开销吗？如果是这样的话，我们可以想象运行上面的过程，并有效地为每个易于验证的问题找到解决方案。这是P与NP的问题。

从直觉上看，答案似乎很明显是“不”(即P != NP)。我们怎么可能模拟无限并行呢？这是几乎每个专家都相信的。但如何证明这一点是一个谜，而且是一个价值100万美元的奖金。

Answer 3

让我们假设魔术师给了我一个“难”问题的解决方案，我可以很容易地验证这个解决方案是否正确。但是，我可以很容易地自己计算这个解决方案吗？(多项式时间)

这正是问题所在。