P！= NP问题 [英] P != NP question

问题描述

这不是一个纯粹的编程问题，但是由于它与编程理论紧密相关，所以我认为最好在这里提出。

Not a 'pure' programming question, but since it is deeply involved in programming theory, I thought it best to ask here.

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

Regarding the P NP problem, this excerpt from http://en.wikipedia.org/wiki/P_versus_NP_problem : "In essence, the question P = NP? asks: Suppose that yes answers to a yes or no question can be verified quickly. Then, can the answers themselves also be computed quickly?"

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

I am left wondering, how is the speed of verifying an answer related to the speed of generating a solution?

推荐答案

从本质上讲，在NP（即不确定性多项式时间）集合中，问题可以在多项式时间中得到验证。问题是，是否可以在多项式时间内确定所有这些问题。

Essentially, in the set of NP, or Nondeterministic Polynomial time, problems, the answer can be verified in polynomial time. The question is whether all such problems can be determined in polynomial time.

如果P = NP为真，并且发现此类算法存在许多问题难以解决但易于验证的解决方案（例如证明）变得像解决一样容易解决。

If P=NP is true, and such algorithms are discovered many problems that are hard to solve but easy to verify the solution, such as proofs, become as easy to solve as to verify.

这篇关于P！= NP问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！