NP-complete reductions

Question

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.

Answer 1

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.

Answer 2

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).