P != NP 问题
这不是一个“纯粹的”编程问题，但由于它深入涉及编程理论，我认为最好在这里问。
关于P NP问题，摘录自http://en.wikipedia.org/wiki/P_versus_NP_problem ：“本质上，问题 P = NP？问：假设可以快速验证是或否问题的“是”答案。那么，答案本身也可以快速计算吗？”
我想知道，验证答案的速度与生成解决方案的速度有何关系？
Not a 'pure' programming question, but since it is deeply involved in programming theory, I thought it best to ask here.
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
假设您有巨大的并行性——无论您想要多少。然后，您可以同时生成所有可能的解决方案，检查其中哪些是正确的，并输出正确的解决方案。在存在无限并行性的情况下，这是一种生成解决方案的方法。 NP 中的问题集是该过程可以快速解决的问题，因为它执行的唯一有趣的计算步骤是检查解决方案是否正确，并且对于 NP 中的问题可以有效地完成此操作。请注意，对于其他一些问题，即使这种并行性也不能让我们快速找到解决方案，因为它要求检查解决方案很容易。
但我们没有无限的并行性。我们能否以某种方式模拟它，而只需要多项式的开销？如果是这样，我们可以想象运行上述过程，并有效地为每个易于验证的问题找到解决方案。这是 P 与 NP 问题。
直观上，答案似乎很明显是“否”（即P！= NP）。我们如何才能模拟无限并行性？这几乎是每个专家都相信的。但如何证明这一点，以及价值100万美元的奖金，却是一个谜。
Suppose you had tremendous parallelism -- however much you wanted. You could then simultaneously generate all possible solutions, check which of these were correct, and output a correct solution. In the presence of infinite parallelism, this is a method of generating a solution. The set of problems in NP are those for which this procedure would work quickly, because the only interesting computational step it is performing is checking whether solutions are correct, and this can be done efficiently for problems in NP. Note that for some other problems, even this parallelism would not allow us to find solutions quickly, since it requires that checking solutions is easy.
But we don't have infinite parallelism. Can we somehow simulate it, with only a polynomial amount of overhead? If so, we could imagine running the above procedure, and efficiently finding solutions for every problem for which verification was easy. This is the P vs. NP question.
Intuitively, it seems clear that the answer is "no" (i.e. P != NP). How could we possibly simulate infinite parallelism? This is what almost every expert believes. But it is a mystery how to prove it, and one that is worth $1,000,000 in prize money.
本质上，在一组 NP（非确定性多项式时间）问题中，可以在多项式时间内验证答案。问题是是否所有此类问题都可以在多项式时间内确定。
如果P=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.
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.
假设魔术师向我提供了一个“难题”的解决方案，我可以轻松验证该解决方案是否正确。但是，我可以轻松地自己计算这个解决方案吗？ （多项式时间）
这正是问题所在。
Let's assume I am handed a solution to a "hard" problem by a magician, and I can easily verify if this solution is correct or not. BUT, can I compute this solution myself easily? (polynomial time)
This is exactly the question.
它可能相关，也可能不相关。
人们关心NP问题是因为我们一直想快速解决它们，但到目前为止我们还没有找到快速解决它们的方法。我们想知道是否有快速的方法来解决这些问题，或者我们是否应该放弃尝试。
It may or may not be related.
People care about NP problems because we want to solve them quickly and all the time, but so far we have not found a way to solve them quickly. We want to know if there a quick way to solve them or if we should give up trying.
这个问题今天已经解决了！
（可能。）
This problem has been solved today!
(Possibly.)
P是可以由确定性图灵机在多项式时间内计算的所有语言的类别。现代计算机非常类似于确定性图灵机，只不过图灵机本质上具有无限的内存。出于实际目的，这种区别通常被忽略。NP是可以由非确定性车削机在多项式时间内计算的所有语言的类别。不确定性图灵机不对应于任何现实世界的设备。计算复杂度的一个基本事实是，
NP等价于验证问题在P中的语言类。事实上，NP有时也被定义为此类；这两个定义是可以互换的，并且验证定义的优点是与现实世界中的确定性图灵机式计算机直接相关。因此，
NP是一类可以在“真实”机器上以多时间方式验证并且可以在非常相似的理论机器上以多时间方式解决的问题。因此，可解决性和可验证性问题是相互联系的。现在，大多数计算机科学家认为
P和NP不等价；也就是说，存在可以由非确定性图灵机在多时间中计算但不能由确定性图灵机计算的语言，或者等效地，存在不能由确定性图灵机在多时间中求解但其解可以在多时间中被验证的语言由确定性图灵机。Pis the class of all languages that can be computed in polynomial time by a deterministic Turing machine. A modern computer is very much like a deterministic Turing machine, except that a Turing machine essentially has infinite memory. This distinction is generally ignored for practical purposes.NPis the class of all languages that can be computed in polynomial time by a non-deterministic Turning machine. A nondeterministic Turing machine does not correspond to any real-world device.It is a basic fact of computational complexity that
NPis equivalent to the class of languages whose verification problems are inP. In fact,NPis sometimes defined as this class; the two definitions are interchangeable, and the verification definition has the benefit of direct relevance to the deterministic-Turing-machine-like computers in the real world.So
NPis the class of problems that are verifiable in poly-time on a "real" machine and solvable in poly-time on a very similar theoretical machine. Thus, the questions of solvability and verifiability are linked.Now, most computer scientists believe that
PandNPare not equivalent; that is, that there exist languages computable in poly-time by a nondeterministic Turing machine but not by a deterministic Turing machine, or equivalently that are not solvable in poly-time by a deterministic Turing machine but whose solutions can be verified in poly-time by a deterministic Turing machine.但这里没有直接关系。可能会有一种直观的感觉，即验证答案比生成答案更容易，因为任何生成的一部分都是为了确保答案是正确的。因此，人们可以采取一种蛮力方法来尝试不同的解决方案，但这往往会导致超出 P 的指数复杂性，或者这就是我几年前在复杂性课程中所记得的。
There isn't a direct relation here though. There may be an intuitive feel that verifying an answer is easier than generating an answer as part of any generation would be to ensure the answer is correct. Thus, one could take a brute force approach to try different solutions but this tends to lead to exponential complexities that are beyond P, or so that is what I recall from Complexity class years ago.
无论它们是否相关，都是克莱普尔基金会的“千年问题”之一，他们将向提供适当证据并经受几年严格检验的人提供一百万美元。
问题的类型比看起来更相关，因为 NP 问题的另一种定义是可以用任意并行计算机有效解决的问题。
人们真正感兴趣的一件事是缺乏证据。有类似问题的证据，但没有这个。这引起了人们，尤其是数学家的兴趣，因为证明可能会给其他事物带来很多见解。佩雷尔曼对庞加莱猜想（另一个千年难题）的证明显然就是这种情况。
另一个问题是这可能产生的影响。目前，很少有人相信存在解决 NP 完全问题的有效方法，因此 P!=NP 的发现几乎没有实际影响。解决 NP 完全问题的有效方法的发现将彻底改变许多计算机科学。它将使很多事情变得更加容易，并且通过使解密变得容易来破坏我们所知道的密码学。
Whether they're related or not is one of the Claypool Foundation's "Millenium Problems", and they'll give a million dollars to somebody providing an appropriate proof that hold up under a few years of intense examination.
The types of questions are more related than they look, since another definition of an NP problem is one that can be solved efficiently with an arbitrarily parallel computer.
One thing that really interests people is the lack of a proof. There are proofs for similar-looking questions, but not this one. That intrigues people, especially mathematicians, since a proof is likely to bring a lot of insight into other things. That is apparently the case for Perelman's proof of the Poincare Conjecture, another of the Millenium Problems.
Another issue is the impact this could have. Right now, few people believe that there is an efficient method for solving NP-complete problems, so a discovery that P!=NP would have little practical impact. A discovery of an efficient way to solve NP-complete problems would revolutionalize a lot of computer science. It would make a lot of things much easier, and would destroy cryptography as we know it by making decryption easy.
不，P=/NP。
答案是 Co-NP-不对称-部分完全
在我的网站上查看我的完整答案：
https://singularariantechnologies.wordpress.com/exponential-breakthroughs-in-epistemology-every-week/
Singularariantechnologies.wordpress.com
基本上总结一下您问题的答案，答案是否定的，一般来说，除了 P=NP 的一种情况外，因此 co-np-不对称部分不完整/完整答案。
为此，我使用 Google.com 作为数据库，它可以在多项式时间内为我提供经过验证的答案，然后我想看看答案是否可以根据多项式的最佳公理化约来计算，该多项式由指数项组成，本质上，答案是，对于两个以上的变量（在本例中为指数），即使我们知道经过验证的答案是什么，答案也是不可计算的。
显然，这实际上让黑帽黑客别无选择，因为未来的加密算法不会那么简单。另外，从技术上讲，这只是 P=NP 的一种情况，因为从公理上讲，多项式必须由多项组成，因此 P=/=NP iff 变量 >= 3 且 P=NP iff 变量 <= 2。
阅读我的完整文档位于我的网站或 Google Drive 上，我还提供了一个指向我的工作的电子表格链接，该链接位于 singleariantechnologies.wordpress.com 上，
这实际上意味着什么？将来不会有黑帽黑客攻击，即使你考虑到通过模二公理地减少加密攻击的尝试，它也无法与高级加密（复杂的多项式加密，带有一些警告和附加功能）一起使用甚至尝试破解密码或其任何加密数据都更加困难..）
No, P=/NP.
The answer is Co-NP-Asymmetric-Partially-Complete
See my full answer here at my website:
https://singularitariantechnologies.wordpress.com/exponential-breakthroughs-in-epistemology-every-week/
Singularitariantechnologies.wordpress.com
To basically summarize the answer to your question, the answer is no, generally, except in one instance where P=NP, ergo the co-np-asymmetric partially incomplete / complete answer.
To do this I used Google.com as a database which could give me a verified answer in polynomial time, and then I wanted to see if the answer would be computable predicated on the best Axiomatic reduction of polynomial, consisting of exponentiated terms and inherently, the answer is that with more than two variables (exponents in this case), the answer is not computable, even though we would know what the verified answer would be.
Obviously this leaves black hat hackers with effectively no alternative, as in the future encryption algorithms will not be so simple. Also, this is technically only one instance where P=NP, because axiomatically, a polynomial must consist of more than one term, ergo P=/=NP iff variables >=3 and P=NP iff variables <= 2.
Read my full documentation on my website or on Google Drive, I also provide a spreadsheet link to my work on singularitariantechnologies.wordpress.com
What does this effectively mean? In the future there will be no black hat hacking, even if you factor in attempts to axiomstically reduce encryption attacks via modulo two, it just won't work with advanced encryption (complex polynomial encryption, with some caveats and bells and whistles to make it much harder to even attempt to break a cipher, or any encrypted data thereof..)