0
$\begingroup$

This action confuses me for a while. As you know, once we come up with a problem and we want to know how hard it is, we will do the "reduction". Intuitively, if we prove problem B is as hard as problem A, we can know the complexity boundary of B. But if problem B is harder than A, why we call the reduction process -- reduce problem A to problem B, not reduce problem B to A?

$\endgroup$
5
$\begingroup$

There are several different types of reduction, but generally, if we say we reduce problem A to problem B, it means something like: if we had a way to solve B, we could use that to solve A. Some reductions may allow to use B as a black box. Others might require that "yes" instances of A map to "yes" instances of B, and that "no" instances map as well. Or, it may be something simpler, like "hey, I already have a great solution to problem B, and now with just a simple transform, I can use it to solve problem A." In all forms, it implies something related to "we could solve A if we had solutions to B".

What that means has something to do with what is known. If B is an easy problem to solve, then A reducing to B tells us that solving A is no harder than solving B, plus doing the reduction from A to B. In that case, an easy reduction, to an easy problem, proves that A is easy.

On the other hand, especially in the context of hardness results, we would usually reduce a known difficult problem (A here) to B, and that would show that, because A is hard, but transforming an instance of A into B is easy, B must also be hard, because if B were easy, it would give a solution to the known A problem.

So basically, for an easy reduction from A to B, it proves 2 things: A is not harder than B, and B is not easier than A. Yes, those are the same thing, but usually, you only care about one of them, depending on whether you know A to be difficult, or B to be easy.

$\endgroup$
  • $\begingroup$ Thank you! Your answer is pretty sufficient! So could I say that -- "reduce" describe the process of "transforming'' the problem A to problem B which might have a good solution already. "Reduce'' does not mean simplify the "problem"? $\endgroup$ – lucasKo Jun 28 '16 at 2:37
  • $\begingroup$ That would be the proper usage if you are reducing to a problem B with a known solution. $\endgroup$ – Algorithms with Attitude Jun 28 '16 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.