A very complex problem in reduction notion

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.