约简概念中一个非常复杂的问题
我已经研究了很多关于减少的内容，但我有一个很糟糕的问题： 我从 CLRS 中得到这一点：
“……通过‘减少’解决问题 A 来解决问题 B，我们用 B 的‘容易性’来证明 A 的‘容易性’。”
我从“Christos H. Papadimitriou 的计算复杂性”中摘录了这一点：
“……如果 B 简化为 A，问题 A 至少与问题 B 一样难。”
我对这两个概念感到困惑： 当我们使用 easiness 时，我们说问题 X 简化为问题 Y，如果我们对 Y 有多项式时间算法并且简化过程在多项式时间内完成，那么问题 X 可以在多项式时间内解决，并且 X 比 Y 更容易，或者至少不是比Y更难
。但是当我们使用硬度时，我们说问题X简化为问题Y，并且Y比X容易或者至少不比X难。
我真的很困惑，请帮助我。 特别感谢。
I have studied many about reduction but I have a bad problem in it:
I take this from CLRS :
" ... by “reducing” solving problem A to solving problem B, we use the “easiness” of B to prove the “easiness” of A."
And I take this from "Computational Complexity by Christos H. Papadimitriou " :
" ... problem A is at least as hard as problem B if B reduces to A."
I got confused with these two notion:
when we use easiness , we say that problem X reduces to problem Y and if we have polynomial time algorithm for Y and reduction process is done in polynomial time then problem X is solvable in polynomial time and X is easier than Y or at least is not harder than Y.
But when we use hardness , we say problem X reduces to problem Y and Y is easier than X or at least is not harder than X.
I really got confused, Please help me.
Special thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我想你可能错过了第一句话说“减少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 困难问题 (Y) 的情况下，通过定义一个方案在多项式时间内构造 NP 困难问题的实例，其解是两个输入数字的总和。这并不意味着加法是 NP 困难的，只是我们让事情变得不必要地困难。使用归约来执行加法是不明智的，因为有更好的方法来执行加法。好吧，最好假设 P!=NP。
I think you might have missed that the first quote says "reduce A to B", and the second quote says "reduce B to A".
If X reduces to Y, meaning that Y can be used to solve X, then X is no harder than Y. That's because polynomial-complexity reduction is considered "free", so by reducing X to Y we've found a way to solve X using whatever solutions there are to Y.
So, in the first quote, if A reduces to B and B is easy, that means A is easy (strictly speaking, it's no harder).
The second quote uses the logical contrapositive: if B reduces to A and B is hard, then A must be hard (strictly speaking, it's no easier). Proof: If A was easy, then B would be easy (as above but A and B are reversed). B is not easy, therefore A is not easy.
Your statement, "we say problem X reduces to problem Y and Y is easier than X or at least is not harder than X" is false. It is possible for X to reduce to Y (that is, we can use Y to solve X), even though Y in fact is harder than X. So we could reduce addition (X) to a special case of some NP-hard problem (Y), by defining a scheme to construct in polynomial time an instance of the NP-hard problem whose solution is the sum of our two input numbers. It doesn't mean addition is NP-hard, just that we've made things unnecessarily difficult for ourselves. It's unwise to use that reduction in order to perform addition, since there are better ways to do addition. Well, better assuming P!=NP, that is.
将归约视为对问题属于某一类的证明的归约，而不是归约问题本身。这种关系更多地与逻辑相关，而不是与复杂性相关。
Think of reduction as reduction of the proof for the problem being in a certain class rather than reducing the problem itself. The relation is more related to logic than to complexity.
理论很简单。
您有一个解决问题 A 的算法，您知道该算法可以在多项式时间内解决。
如果可以将问题 B 转换为问题 A 可以解决的符号，然后在多项式时间内将结果转换回问题 B 的符号，那么解决问题 B 也将在多项式时间内 - 作为总时间只是两个多项式的加法 - 因此并不难。
The theory is simply this.
You have an algorithm to solve problem A that you know can be solved in polynominal time.
If it is possible to convert problem B into a notation that can be solved by problem A and then convert the result back into the notation for problem B in polynominal time, then to solve problem B will also be in polynominal time - as the total time is just the addition of two polynominals - hence no harder.