I've read that "Every problem in NP can be reduced to every NP-complete problem".

My question is on the choice of the word "reduce". If I were to "reduce" a polynomial problem in NP to an exponential problem in NP, I just plain feel weird about using the word "reduce" because I feel like I've increased the problem, not reduced it. So, why do we use the word reduce?

Also, why do we write "reduce A to B" as $A\le_{p} B$. It seems backwards.

  • 8
    $\begingroup$ Just a hint: "$A$ can be reduced to $B$" means (informally) that $A$ is easier than or has the same difficulty of $B$. So you can view the $\leq_p$ like an order in a "scale of increasing difficulty". A reduction from $A$ to $B$ means (very informally) that $A$ can be considered an easier variant of an harder problem $B$, and if we know how to solve $B$ then we can also solve $A$ without too much computation overhead: just the (polynomial) time needed to transform an instance of the problem $A$ to a proper instance of the problem $B$. $\endgroup$ – Vor Nov 26 '12 at 9:10
  • 3
    $\begingroup$ @Vor move it to an answer? $\endgroup$ – Realz Slaw Nov 26 '12 at 17:12

A reduction from A to B shows that A is "no harder" than B in some sense. We call it a reduction because it reduces the problem of solving A to the problem of solving B. This is a usage of the word "reduce" that is more mathematical and less about "size"; you can think of it as meaning that we've reduced the amount of work the world has to do, because even though we haven't solved A or B with the reduction we've made it so that a solution to B will automatically also be a solution to A.

Where A was a problem we didn't have any efficient solutions for, and where we already have an efficient solution for B, this does result in A getting "smaller" in a sense. For example, say we'd already come up with an exponential solution to A, and B is an NP-complete problem. Previously, the best we knew was that A was an exponential problem. After someone comes up with the A -> B reduction, now we know it's actually an NP problem.

Yes, you can use a reduction argument to show that an already-known-to-be-easy problem is "no harder" than a hard problem. You can in fact use a polynomial-time reduction from ANY problem in P to ANY other problem whatsoever (that has at least one "yes" instance and at least one "no" instance), because you can "solve" the P problem in the reduction but simply encode the answer as an instance of another problem. Yes, this is pointless. But it's not "wrong" or inconsistent.

The problem you're having is purely in the analogy you're using, namely that a reduction is a "way of making a problem smaller". That is a reasonable metaphor for one of the usual aims of reduction proofs, which is to show that a problem is "easier" than previously suspected by finding a way to reduce it to another problem already known to be "easier".

But that doesn't help you with the other extremely common use of reduction arguments, which is to show that a problem C is impossible to solve, by finding a reduction from another problem D which is already known to be impossible. Here the reduction argument isn't "making D smaller", it's showing that C is "big".

Try to think of a reduction argument from A -> B as a way of showing that A is "no harder" than B. When you think of it that way, it's not at all surprising that you can often reduce easy problems to hard ones; we already knew that they were easier! This account also easily explains the incomputability proofs by reduction; if the Halting Problem is no harder than X, then X can't be solvable.


Mostly from Vor's comment:

$A \le_pB$ can be taken to mean that the problem $A$ is at least as easy as $B$ (or less hard). The $_p$ subscript stands for polynomial-time and indicates that "easy" is relative term here, and the difficulty of the actual problems must consider the polynomial-time reduction as inconsequential (such as when solving $B$ requires super-polynomial time).

  • 1
    $\begingroup$ Shall I make this a community wiki? $\endgroup$ – Realz Slaw Dec 5 '12 at 19:00
  • $\begingroup$ This doesn't answer the question about why we use the terms reduce/reduction. $\endgroup$ – rambo coder Dec 5 '12 at 22:45

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.