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

Question

我试图恢复密码.考虑到这一点,我认识到"密码恢复"这个问题是NP问题的一个很好的例子.如果您知道密码,则很容易在多项式时间内验证密码.但是如果您不知道密码,则必须在整个空间内搜索可能显示为指数时间的可能解决方案.

现在我的问题是:这不是证明P!= NP,因为"密码恢复"是NP的一个元素,可以显示需要多于多项式时间来运行？

Answer 1

如果您显示任何解决"密码恢复"的算法需要多于多项式时间,那么它确实证明P≠NP.

否则,如果您只显示一个特定解决方案需要多于多项式时间,则它不会显示任何内容.我可以编写一个排序来要求指数时间(shuffle数组直到它被排序),但这并不意味着没有多项式解决方案.

Answer 2

NP并不意味着"非多项式",如果这就是你的想法(如果你不是,我会提前道歉!).它意味着"非确定性多项式".非确定性算法是等同于算法的无限数量的并行实例的算法.例如,通过暴力找到正确的密码是非确定性多项式:如果您想象检查密码,如果您的猜测恰好是正确的,则在密码长度上采用线性(即多项式)时间,但您需要并行检查任意数量的可能密码(k ^ n),然后使用此方法找到解决方案的成本是非确定性多项式.

非确定性算法也可以被认为是其状态在某些步骤分支的算法.一个简单的例子就是一个非确定性有限自动机(NFA) - 有时你不知道状态之间要采用什么边缘,所以你要把它们都拿走.很容易证明每个NFA都等同于一个确定性的FA,因此认为同样可以用于其他有趣的算法类别是很诱人的.不幸的是,对于多项式算法的一般情况很难这样做,并且一般怀疑它们不是等价的,即P!= NP.

Answer 3

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

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