这个 P != NP 证明缺少什么？
我尝试找回密码。当想到这一点时，我认识到“密码恢复”问题是 NP 问题的一个很好的例子。如果您知道密码，则很容易在多项式时间内验证它。但是，如果您不知道密码，则必须搜索整个可能的解决方案，这可能会花费指数时间。
现在我的问题是：这是否表明 P != NP 因为“密码恢复”是 NP 的一个元素，可以证明需要超过多项式的时间来运行？
I tried to recover a password. When thinking of this I recognized that the problem "password recovery" is a very nice example of a NP problem. If you know the password it's very easy to verify it in polynomial time. BUT if you don't know the password you have to search the whole space of possible solutions which can be shown to take exponential time.
Now my question is: Doesn't this demonstrate that P != NP since "password recovery" is an element of NP that can be shown to require more than polynomial time to run?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
如果您证明任何解决“密码恢复”问题的算法都需要超过多项式时间，那么它确实证明了 P ≠ NP。
否则，如果您仅表明一个特定解决方案需要超过多项式的时间，那么它什么也证明不了。我可以编写一个需要指数时间的排序（随机排列数组直到排序），但这并不意味着没有多项式解决方案。
If you show that any algorithm that solves "password recovery" requires more than polynomial time, then it does demonstrate that P ≠ NP.
Otherwise, if you only show that one particular solution requires more than polynomial time, it demonstrates nothing. I can write a sort to require exponential time (shuffle array until it's sorted), but that doesn't mean there's no polynomial solution.
NP 并不意味着“非多项式”，如果您是这么想的话（如果您不是这么想的话，我提前道歉！）。它的意思是“非确定性多项式”。非确定性算法相当于一种算法的无限数量的并行实例。举个例子，通过暴力破解找到正确的密码是非确定性多项式：如果你想象检查密码，如果你的猜测碰巧是正确的，则需要密码长度的线性（即多项式）时间，但你需要并行检查任意数量的可能密码 (k^n)，则使用此方法找到解决方案的成本是非确定性多项式。
非确定性算法也可以被认为是在某些步骤发生状态分支的算法。一个简单的例子是非确定性有限自动机 (NFA)——有时您不知道在状态之间采用什么边缘，因此您将两者都采用。很容易证明每个 NFA 都等价于确定性 FA，因此很容易想到可以为其他有趣的算法类别证明同样的情况。不幸的是，对于多项式算法的一般情况很难做到这一点，并且普遍怀疑它们不等价，即 P != NP。
NP does not mean "nonpolynomial", if that's what you were thinking (and my apologies in advance if you were not!). It means "nondeterministic polynomial". A nondeterministic algorithm is one that's equivalent to an unbounded number of parallel instances of an algorithm. As an example, finding the correct password by brute force is nondeterministic polynomial: if you imagine that checking the password, if your guess happens to be correct, takes linear (i.e. polynomial) time on the length of the password, but that you need to check an arbitrary number of possible passwords (k^n) in parallel, then the cost of finding the solution using this method is nondeterministic polynomial.
A nondeterministic algorithm can also be thought of one whose state branches at some steps. A simple example of this is a nondeterministic finite automaton (NFA) -- sometimes you don't know what edge to take between states, so you take them both. It's easy to show that every NFA is equivalent to a deterministic FA, and so it is tantalising to think the same could be proved for other interesting classes of algorithm. Unfortunately it's hard to do so for the general case of polynomial algorithm, and the general suspicion is that they are not equivalent, i.e. that P != NP.
问题属于 NP 的推理是正确的：如果它可以在多项式时间内验证，那么它属于 NP。即使是非常简单的问题也是 NP 问题。基本上所有的P都包含在NP中。 (*)
现在，您可以通过一种方法将其转化为 P != NP 的证明：
1) 表明“密码恢复”是 NP 完全的。也就是说，任何NP问题都可以在多项式时间内简化为“密码恢复”。 （即有一个有效的算法可以将任何其他 NP 问题转换为“密码恢复”。）
2）一旦你有了它，正如 Pavel Shved 提到的那样，仅仅表明直观算法是非多项式是不够的。你必须证明不存在多项式算法来解决“密码恢复”问题。这是一项非常艰巨的任务。
(*) Edmund 也是对的：NP 表示非确定性机器上的多项式。多项式验证本质上是非确定性机器选择的路径。
The reasoning that the problem is in NP is correct: if it can be verified in polynomial time, it's in NP. Even very simple problems are in NP. Basically, all of P is included in NP. (*)
Now, here is one way you could go about turning this into a proof that P != NP:
1) Show that "password recovery" is NP-complete. That is, any problem in NP can be reduced to "password recovery" in polynomial time. (i.e. there is an efficient algorithm to convert any other NP problem to "password recovery".)
2) Once you have that then, as Pavel Shved mentions, it is not enough to show that the intuitive algorithm is non-polynomial. You have to show that there does not exist a polynomial algorithm to solve "password recovery". A very difficult task.
(*) Edmund is also right: NP means polynomial on a non-deterministic machine. A polynomial verification is essentially the path chosen by the non-deterministic machine.
n个不同整数有n!种排列，但只有一个按升序排序，但我们可以在n log n中找到它> 时间。有关更有趣的示例，请参阅 Project Euler #67。有关 P/NP/ 等的详细信息。请参阅上一个问题。
n!permutations of a set ofndistinct integers but only one is sorted ascending yet we can find it inn log ntime. For a more fun example, see Project Euler #67.For details on P/NP/etc. see this previous question.
问题并不表明密码恢复是非多项式的，因为显然它是——你必须搜索答案的指数空间。
实际上，“密码恢复”并不是对标准计算问题的真正描述。从形式上看，密码破解算法似乎采用某种“预言机”来回答给定的字符串是否是正确的密码。然而，P 和 NP 是根据图灵机定义的，图灵机以字符串作为输入。
The problem is not showing that password recovery is non-polynomial, since clearly it is -- you have to search an exponential space of answers.
Actually, "password-recovery" isn't really a description of a standard computational problem. It seems that, formally, password breaking algorithms take some sort of "oracle" that can answer whether a given string is the correct password. However, P and NP are defined in terms of Turing machines, which take strings as input.
该问题的正式表述是接受哈希值（和盐）作为输入，并尝试查找将生成该哈希的密码：基本已知的密文冲突查找问题。
根据哈希的质量，这可能不需要需要指数时间。事实上，许多广泛使用的加密散列已经识别出比密钥空间搜索运行得更快的攻击。
这就是说：您（和其他一些响应者）假设密码修改例程具有设计者希望它们具有的所有属性。这必须被证明。
The formal statement of this problem would be one that accepts as input the hashed value (and salt) and attempts to find a password that will generate that hash: your basic known cyphertext collision finding problem.
Depending on the quality of the hash, this might not require exponential time. Indeed, many cryptographic hashed in widespread use have identified attacks that run faster than keyspace searches.
Which is to say: you (ans some of the other responders) have assumed that the password munging routine has all the properties the designers wanted them to have. This would have to be proved.
写这个答案是因为我在某个时候有过这个想法，而这里的答案并不令人满意。
你已经证明了在“Oracle”存在的情况下 P =/= NP （这是告诉密码是否正确的东西）。
事实证明，您实际上无法使用预言机来证明原始的 P 与 NP（这种技术称为相对化）。
为了证明最初的问题，你必须用图灵机来定义 Oracle。换句话说，您必须描述密码验证程序对输入执行的操作，然后证明没有算法可以在给定密码验证程序代码的情况下猜测密码。
请注意，您必须对任何可能的快速密码验证程序执行此操作。密码验证器算法的唯一要求是它在密码长度方面以多项式时间运行。
因此，给定任何可能的算法来检查密码在多项式时间内是否正确，您必须编写一个算法来读取验证者算法并尝试猜测密码是否在多项式时间内。如果你能证明或反驳这种算法的存在，那么你就解决了问题。
Writing this answer because I had this idea at some point, and the answers here were not satisfactory.
You have proved that P =/= NP under the presence of an 'Oracle' (this is the thing that tells if the password is right or not).
It has been shown you can actually not prove the original P vs NP by using Oracles (this technique is called relativisation).
In order to prove the original problem you have to define the Oracle in terms of a turing machine. In other words, you have to describe what the password verifier does with the input, and then prove that there is no algorithm that can guess the password given the password verifier code.
Note that you have to do this for any possible fast password verifier. The only requirement of the password verifier algorithm is that it runs in polinomial time with regards to the password length.
So given any possible algorithm that checks if the password is right or not in polinomial time, you have to write an algorithm that reads the verifier algorithm and tries to guess the password is in polinomial time. If you can prove or disprove that such algorithm exists then you have solved the problem.