如果 Y 可以在多项式时间内还原为 X，那么 X 至少和 Y 一样硬是怎么回事？
If Y is reducible to X in polynomial time, then how is it true that X is at least as hard as Y?
我很难理解两个 类 问题的复杂性之间的关系，比如 NP-hard 和 NP-complete 问题。
处的答案指出：
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 困难问题至少和 NP 完全问题一样难。
这有什么意义？我哪里有思维错误？
设 I_X 为 X 的指示函数（即，如果输入在 X 中则为 1，否则为 0），I_Y 为 Y 的指示函数。如果 Y 通过可以在多项式时间内计算的函数 f，然后 I_Y = I_X 。 f，哪里。表示函数组合。 X 至少和 Y 一样难，因为给定 I_X 的算法，上面的公式给出了 I_Y 的算法，对于 运行 次中的任何 class 次关闭多项式替换（例如，多项式、指数、有限），如果 I_X 的算法属于 class，那么 I_Y 的算法也是如此。这个说法的反面是，如果Y没有快速决策程序，那么X也没有快速决策程序。
你的错误是假设你必须解决X才能解决Y。Y实际上可能更容易，但解决它的一种方法是将其更改为X问题的一个实例。由于我们使用大 O 表示法和 NP class，我们远远超过了线性算法，您始终可以安全地丢弃算法的任何线性部分。在解决 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-complete class.
另一个例子：假设卷积在我的 "complete" 集合中，通常需要 O(n²)。然后你想出了 O(n * log(n)) 的快速傅立叶变换，你发现你可以通过将它转换为 FFT 问题来解决卷积问题。现在你想出了一个卷积的解决方案，它是 o(n²)，更具体地说是 O(n * log(n)).
我很难理解两个 类 问题的复杂性之间的关系，比如 NP-hard 和 NP-complete 问题。
处的答案指出：
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
Xis NP-hard, if there is an NP-complete problemY, such thatYis reducible toXin polynomial time.
如果一个问题Y可以多项式时间化简为X，难道不是说Y至少和X一样难吗？如果一个问题 Y 在多项式时间内可以简化为 X，那么求解 Y 所需的时间就是多项式时间 + 求解 X 所需的时间。所以在我看来问题 Y 至少和 X.
但上面引用的文字恰恰相反。它说，如果一个 NP 完全问题 Y 可以简化为一个 NP 困难问题 X，那么 NP 困难问题至少和 NP 完全问题一样难。
这有什么意义？我哪里有思维错误？
设 I_X 为 X 的指示函数（即，如果输入在 X 中则为 1，否则为 0），I_Y 为 Y 的指示函数。如果 Y 通过可以在多项式时间内计算的函数 f，然后 I_Y = I_X 。 f，哪里。表示函数组合。 X 至少和 Y 一样难，因为给定 I_X 的算法，上面的公式给出了 I_Y 的算法，对于 运行 次中的任何 class 次关闭多项式替换（例如，多项式、指数、有限），如果 I_X 的算法属于 class，那么 I_Y 的算法也是如此。这个说法的反面是，如果Y没有快速决策程序，那么X也没有快速决策程序。
你的错误是假设你必须解决X才能解决Y。Y实际上可能更容易，但解决它的一种方法是将其更改为X问题的一个实例。由于我们使用大 O 表示法和 NP class，我们远远超过了线性算法，您始终可以安全地丢弃算法的任何线性部分。在解决 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-complete class.
另一个例子：假设卷积在我的 "complete" 集合中，通常需要 O(n²)。然后你想出了 O(n * log(n)) 的快速傅立叶变换，你发现你可以通过将它转换为 FFT 问题来解决卷积问题。现在你想出了一个卷积的解决方案，它是 o(n²)，更具体地说是 O(n * log(n)).