这个P != NP证明缺少什么？

Question

我试着恢复密码。当我想到这一点时，我意识到“密码恢复”问题是NP问题的一个很好的例子。如果你知道密码，就很容易在多项式时间内验证它。但是如果你不知道密码，你必须搜索整个可能的解决方案空间，这可能会花费指数级的时间。

现在我的问题是:这不是证明了P != NP吗，因为“密码恢复”是NP的一个元素，可以证明它需要多项式时间才能运行？

Answer 1

问题并不是密码恢复是非多项式的，因为很明显它是--您必须搜索答案的指数空间。

实际上，“密码恢复”并不是对标准computational problem的真正描述。从形式上讲，密码破解算法似乎需要某种“预言机”来回答给定的字符串是否为正确的密码。然而，P和NP是根据图灵机定义的，图灵机将字符串作为输入。

Answer 2

如果您证明了任何解决“密码恢复”的算法都需要多项式时间，那么它确实证明了P≠NP。

否则，如果只显示一个特定的解决方案需要超过多项式的时间，则不会说明任何问题。我可以编写一个需要指数级时间的排序(在排序之前对数组进行混洗)，但这并不意味着没有多项式解。

Answer 3

NP并不意味着“非多项式”，如果这是您所想的(如果您不是这样想的，请提前向您道歉！)它的意思是“非确定性多项式”。非确定性算法等同于算法的无限多个并行实例。例如，通过暴力破解找到正确的密码是不确定的多项式:如果您想象检查密码，如果您的猜测是正确的，则需要在密码长度上花费线性(即多项式)时间，但您需要并行检查任意数量的可能密码(k^n)，那么使用此方法找到解决方案的成本是不确定的多项式。

非确定性算法也可以被认为是状态在某些步骤分支的算法。这方面的一个简单示例是非确定有限自动机(NFA) --有时您不知道在状态之间采用哪一条边，所以您将两者都采用。很容易证明每个NFA都等同于一个确定性FA，因此认为其他有趣的算法类也可以证明这一点是很诱人的。不幸的是，对于一般的多项式算法很难做到这一点，一般的怀疑是它们不是等价的，即P != NP。