algorithm - 如果 Y 可以在多项式时间内还原为 X，那么 X 至少和 Y 一样硬是怎么回事？

Question

我很难理解两类问题的复杂性之间的关系，比如 NP-hard 问题和 NP-complete 问题。

答案在 https://stackoverflow.com/a/1857342/状态:

NP Hard

Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.

The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

如果有问题Y可以减少到X在多项式时间内，我们不应该说Y吗？至少和X一样难？如果有问题Y可简化为 X在多项式时间内，那么解决 Y 所需的时间是多项式时间+求解X所需的时间.所以在我看来这个问题Y至少和X一样难.

但是上面引用的文字说的恰恰相反。它说，如果一个 NP 完全问题 Y可简化为 NP 难问题 X , 那么 NP-hard 问题至少和 NP-complete 问题一样难。

这有什么意义？我的思维哪里出了问题？

Answer 1

您的错误是假设您必须解决 X 才能解决 Y。Y 实际上可能更容易，但解决它的一种方法是将其更改为 X 问题的实例.由于我们采用大 O 表示法并且在 NP 类中，我们远远超过了线性算法，因此您始终可以安全地丢弃算法的任何线性部分。在解决 P=NP 问题之前，您几乎可以安全地丢弃任何多项式部分。这意味着 O(f(n) + n) = O(f(n)) 其中 n=O(f(n))。

示例(这显然既没有 NP-hard 问题也没有 NP-完全问题，而只是一个例子):你要在 n 个数字的未排序数组中找到最小的数字。有一个明显的解决方案可以遍历整个列表并记住您找到的最小数字，非常简单和可靠的 O(n)。

有人过来说，好吧，我们改成对数组排序，然后我们就可以取第一个数字，它就是最小的。请注意，问题的这种转换是 O(1)，但我们可以假设必须对数组进行一些预处理，使其成为 O(n)。整体解是O(n + n*log(n)) = O(n * log(n))。

在这里你也把简单的问题变成了困难的问题，从而证明困难的问题确实和简单的问题一样或更难。

NP-hard 问题定义的基本含义是，X 至少与 NP-complete Y 问题一样难。如果你发现一个 NP-complete Y 问题，你可以通过解决 X 问题来解决，这意味着要么 X 和 Y 一样难，要么比 Y 更难，那么它确实是 NP-hard，或者如果它更简单，这意味着你找到了一个比以往任何算法都更快地求解 Y 的算法，甚至有可能将其移出 NP 完全类。

另一个例子:假设卷积在我的“完整”集合中，并且通常需要 O(n²)。然后你想出了 O(n * log(n)) 的快速傅立叶变换，你发现你可以通过将它转换为 FFT 问题来解决卷积问题。现在你想出了一个卷积的解决方案，它是 o(n²)，更具体地说是 O(n * log(n))。