9

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

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

4

7 回答 7

20

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

否则，如果您只证明一个特定的解决方案需要的时间超过多项式时间，那么它什么也证明不了。我可以编写一个需要指数时间的排序（随机排列数组直到它被排序），但这并不意味着没有多项式解决方案。

于 2009-12-12T09:01:59.243 回答
8

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

一种非确定性算法也可以被认为是在某些步骤中状态分支的算法。一个简单的例子是非确定性有限自动机（NFA）——有时你不知道在状态之间取什么边，所以你把它们都取了。很容易证明每个 NFA 都等价于确定性 FA，因此认为对于其他有趣的算法类别也可以证明相同是很诱人的。不幸的是，对于多项式算法的一般情况，很难做到这一点，而且普遍怀疑它们是不等价的，即 P != NP。

于 2009-12-12T09:06:03.290 回答
4

问题在 NP 中的推理是正确的：如果可以在多项式时间内验证，那么它在 NP 中。即使是非常简单的问题也在 NP 中。基本上，所有的 P 都包含在 NP 中。(*)

现在，这里有一种方法可以将其转化为 P != NP 的证明：

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

2）一旦你有了它，正如 Pavel Shved 所提到的，仅仅证明直觉算法是非多项式的是不够的。您必须证明不存在解决“密码恢复”问题的多项式算法。一项非常艰巨的任务。

(*) Edmund 也是对的：NP 表示非确定性机器上的多项式。多项式验证本质上是非确定性机器选择的路径。

于 2009-12-12T09:43:35.320 回答
2
  1. 如前所述，“密码恢复”不是决策问题。
  2. 您还没有证明“密码恢复”没有多项式时间算法，您只是根据直觉证明它没有。解决方案空间巨大并不意味着没有快速算法可以找到解决方案；例如，有n!一组n不同整数的排列，但只有一个是按升序排序的，但我们可以及时找到它n log n。有关更有趣的示例，请参阅Project Euler #67。
  3. 即使您确实将“密码恢复”改写为一个决策问题并且能够证明不存在用于解决它的多项式时间算法，您现在也必须证明“密码恢复”是 NP 完全的。

有关 P/NP/等的详细信息。看到这个以前的问题。

于 2009-12-12T09:56:57.493 回答
1

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

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

于 2009-12-12T09:46:27.857 回答
1

这个问题的正式陈述将是接受散列值（和盐）作为输入并尝试找到将生成该散列的密码：您的基本已知密文冲突查找问题。

根据散列的质量，这可能不需要指数时间。事实上，许多广泛使用的加密哈希已经识别出比密钥空间搜索运行得更快的攻击。

也就是说：您（以及其他一些响应者）已经假设密码修改例程具有设计者希望他们拥有的所有属性。这必须得到证明。

于 2009-12-12T17:17:22.267 回答
0

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

您已经证明 P =/= NP 在“Oracle”的存在下（这是告诉密码是否正确的东西）。

已经表明，您实际上无法通过使用 Oracle 来证明原始 P 与 NP（这种技术称为相对化）。

为了证明原始问题，您必须根据图灵机来定义 Oracle。换句话说，你必须描述密码验证器对输入做了什么，然后证明没有算法可以猜测给定密码验证器代码的密码。

请注意，您必须为任何可能的快速密码验证程序执行此操作。密码验证器算法的唯一要求是它在密码长度方面以多项式时间运行。

因此，给定任何可能的算法来检查密码是否在多项式时间内正确，您必须编写一个算法来读取验证者算法并尝试猜测密码是否在多项式时间内。如果你能证明或反驳这种算法的存在，那么你就解决了这个问题。

于 2018-01-21T22:21:20.117 回答