此P！= NP证明缺少什么？

Question

我试图恢复密码。考虑到这一点时，我认识到问题“密码恢复”是NP问题的一个很好的例子。如果您知道密码，则很容易在多项式时间内进行验证。但是，如果您不知道密码，则必须搜索所有可能的解决方案的空间，这些解决方案可以证明需要花费指数时间。

现在我的问题是：这不是证明p！= np，因为“密码恢复”是NP的一个元素，可以证明需要运行的多项式时间更多吗？

Answer 1

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

实际上，“密码恢复”并不是对标准的描述 计算问题. 。似乎，正式地，密码破坏算法采用某种“甲骨文”，可以回答给定的字符串是否是正确的密码。但是，p和np是根据图灵机的定义，这些计算机将字符串作为输入。

Answer 2

如果你表明 任何 求解“密码恢复”的算法比多项式时间需要更多，然后确实证明了p≠np。

否则，如果您只显示 一个特殊的解决方案 不仅需要多项式时间，还没有任何证明。我可以编写一种需要指数时间的时间（洗牌数组直到排序），但这并不意味着没有多项式解决方案。

Answer 3

NP并不意味着“非分解”，如果这是您的想法（如果您不在的话，请提前道歉！）。它的意思是“非确定性多项式”。非确定算法是一种等同于无限数量的算法的平行实例。例如，通过蛮力找到正确的密码是不确定的多项式：如果您想象检查密码，如果您的猜测恰好是正确的，请在密码的长度上进行线性（即多项式）时间，但是您需要需要并行检查任意数量的可能密码（k^n），然后使用此方法找到解决方案的成本是无确定的多项式。

也可以想到一种非确定算法是一个在某些步骤中的州分支机构的算法。一个简单的例子是一个非确定的有限自动机（NFA） - 有时您不知道在状态之间要采取什么边缘，因此您将它们都置于两者之间。很容易证明每个NFA都等同于确定性的FA，因此可以证明可以证明其他有趣类别的算法可以证明相同的算法是诱人的。不幸的是，对于多项式算法的一般情况很难做到这一点，并且普遍怀疑它们不是等效的，即p！= np。

Answer 4

问题在NP中的原因是正确的：如果可以在多项式时间内对其进行验证，则在NP中。即使是非常简单的问题，也在NP中。基本上，所有P都包含在NP中。 （*）

现在，这是您可以将其转变为P！= NP的一种方法：

1）证明“密码恢复”是NP完成的。也就是说，在多项式时间内，NP中的任何问题都可以简化为“密码恢复”。 （即有一种有效的算法将任何其他NP问题转换为“密码恢复”。）

2）一旦有了它，正如帕维尔（Pavel）提到的那样，就不足以证明直觉算法是非多项式的。您必须证明不存在用于求解“密码恢复”的多项式算法。一项非常艰巨的任务。

（*）埃德蒙（Edmund）也是正确的：NP在非确定性机器上表示多项式。多项式验证本质上是非确定性机器选择的路径。

Answer 5

1. 如前所述，“密码恢复”不是决策问题。
2. 您尚未证明“密码恢复”没有多项式时间算法，您只是以直观的理由争论它没有。仅仅因为解决方案空间是巨大的，并不意味着没有快速算法可以找到解决方案。例如，有 n! 一组 n 独特的整数，但只有一个正在排序，但我们可以在 n log n 时间。有关一个更有趣的例子，请参阅 Euler项目＃67.
3. 即使您确实将“密码恢复”作为决策问题，并且能够证明没有一个多项式时间算法来解决该算法，您现在必须证明“密码恢复”是NP-Complete。

有关P/NP/等的详细信息。看到这个 上一个问题.

Answer 6

该问题的正式陈述将是接受Hashed值（和盐）的输入，并试图找到 一个 将生成该哈希的密码：您的基本已知Cyphertext碰撞查找问题。

根据哈希的质量，这个 也许不会 需要指数时间。实际上，许多广泛使用中的密码函数都已经确定了比键空间搜索更快的攻击。

也就是说：您（其他一些响应者） 假定 密码弹出的例程具有设计师希望他们拥有的所有属性。这必须是 证明.

Answer 7

写这个答案是因为我在某个时候有这个想法，而这里的答案并不令人满意。

您已经证明了p =/= np在“ oracle”的存在下（这是告诉密码是否正确的原因）。

已经证明您实际上无法通过使用Oracles证明原始的P VS NP（此技术称为相对化）。

为了证明原始问题，您必须根据图灵机定义甲骨文。换句话说，您必须描述密码验证者对输入的操作，然后证明没有算法可以猜测给定密码验证符代码的密码。

请注意，您必须为任何可能的快速密码验证符执行此操作。密码验证算法的唯一要求是，它在密码长度方面运行。

因此，考虑到任何可能在多元时间内检查密码是否正确的算法，您必须编写一种读取读取验证者算法的算法，并试图猜测密码在多元时间时间。如果您可以证明或反驳这种算法存在，那么您已经解决了问题。