这个P！= NP证明缺少什么？
我试图恢复密码。 在想到这一点时，我认识到“密码恢复”这个问题是NP问题的一个很好的例子。 如果您知道密码，可以很容易地在多项式时间内进行验证。 但是如果您不知道密码，您必须搜索可能会出现指数时间的可能解决方案的整个空间。
现在我的问题是：这是否证明P！= NP，因为“密码恢复”是NP的一个元素，可以显示它需要超过多项式时间才能运行？
问题并不是显示密码恢复是非多项式的，因为显然它是 - 您必须搜索指数空间的答案。
实际上，“密码恢复”实际上不是对标准计算问题的描述。 从形式上看，密码破译算法似乎需要某种“oracle”来回答给定的字符串是否是正确的密码。 然而，P和NP是根据图灵机来定义的，它以字符串作为输入。
如果表明任何解决“密码恢复”的算法都需要多于多项式时间，那么它确实证明P≠NP。
否则，如果只显示一个特定的解决方案需要多于多项式时间，那么它什么也没有。 我可以编写一个排序来要求指数时间（洗牌数组，直到排序），但这并不意味着没有多项式解决方案。
NP并不意味着“非多项式”，如果这就是你的想法（如果你不是这样的话，我会提前道歉）。 它意味着“不确定多项式”。 非确定性算法就相当于算法的无限并行实例。 作为一个例子，通过暴力破解找到正确的密码是非确定性的多项式：如果你想象检查密码，如果你的猜测恰好是正确的，那么密码的长度就需要线性（即多项式）时间，但是你需要并行检查任意数量的可能密码（k ^ n），那么使用这种方法找到解决方案的代价是非确定性多项式。
非确定性算法也可以被认为是在某些步骤中状态分支的算法。 一个简单的例子就是一个非确定型有限自动机（NFA） - 有时候你不知道在状态之间应该采取什么样的边界，所以你把它们都拿走了。 很容易证明每个NFA都等价于一个确定性的FA，所以很容易想到可以为其他有趣的算法类证明相同的结果。 不幸的是，对于多项式算法的一般情况来说很难做到这一点，并且一般的怀疑是它们不是等价的，即P！= NP。
链接地址: http://www.djcxy.com/p/39979.html