我研究了很多关于减少的问题，但我有一个很糟糕的问题：我从 CLRS 得到这个：
“ ...通过将解决问题 A 的问题“简化”为解决问题 B，我们用 B 的“容易性”来证明 A 的“容易性”。”
我从“Christos H. Papadimitriou 的计算复杂性”中得到这个：
“……如果 B 简化为 A，问题 A 至少和问题 B 一样难。”
我对这两个概念感到困惑：当我们使用 easyiness 时，我们说问题 X 减少为问题 Y，如果我们有 Y 的多项式时间算法并且减少过程是在多项式时间内完成的，那么问题 X 可以在多项式时间内解决，而 X 是比 Y 容易，或者至少不比 Y 难。
但是当我们使用 hard 时，我们说问题 X 简化为问题 Y，并且 Y 比 X 更容易，或者至少不比 X 更难。
我真的很困惑，请帮助我。特别感谢。
我想你可能错过了第一个引用说“将 A 减少到 B”，而第二个引用说“将 B 减少到 A”。
如果 X 归约为 Y，意味着 Y 可以用来求解 X，那么 X 并不比 Y 难。那是因为多项式复杂性归约被认为是“免费的”，所以通过将 X 归约为 Y，我们找到了一种解决方法X 使用 Y 的任何解决方案。
所以，在第一个引用中，如果 A 简化为 B 并且 B 很容易，那意味着 A 很容易（严格来说，它并不难）。
第二个引用使用逻辑对立：如果 B 简化为 A 并且 B 是硬的，那么 A 一定是硬的（严格来说，这并不容易）。证明：如果 A 很容易，那么 B 也很容易（如上所述，但 A 和 B 是相反的）。B不容易，所以A不容易。
您的陈述，“我们说问题 X 简化为问题 Y，并且 Y 比 X 容易，或者至少不比 X 难”是错误的。X 有可能归约为 Y（也就是说，我们可以使用 Y 来求解 X），即使 Y 实际上比X 更难。所以我们可以将加法（X）归约为某个 NP-hard 问题的特殊情况(Y)，通过定义一个方案来在多项式时间内构造一个 NP-hard 问题的实例，其解决方案是我们两个输入数字的总和。这并不意味着加法是 NP 难的，只是我们给自己制造了不必要的困难。使用这种减少来执行加法是不明智的，因为有更好的方法来进行加法。好吧，最好假设 P!=NP，也就是说。
将归约视为对某个类中问题的证明的归约，而不是归约问题本身。这种关系更多地与逻辑有关，而不是与复杂性有关。
理论就是这样。
你有一个算法来解决你知道可以在多项式时间内解决的问题 A。
如果可以将问题 B 转换为问题 A 可以解决的符号，然后将结果转换回多项式时间内问题 B 的符号，那么解决问题 B 也将在多项式时间内 - 作为总时间只是两个多项式的加法 - 因此没有更难。