Why is reduction mostly associated with proving hardness?

Question

Reduction is a powerful problem solving technique that is helpful in solving problems in terms of the solution to other problems, it can also be used for complexity analysis. Why does most of the literature restrict mentioning reduction to proving hardness which seems to be a pessimistic point of view for reduction (unless P=NP ofcourse :) )?

EDIT: Just to make sure my question is well understood. I am aware that reduction is used for problem solving and designing or analyzing algorithms, I have solved hundreds of contest problems with reduction which leads to my question of why is a random search for reduction lead to the NP completeness context with book chapters and papers illustrating its power from the complexity theory point of view when the same basic definition for reduction can be used for designing algorithms but just rarely (or implicitly) mentioned. In other words, why does a random sampling of the occurrences of the term "reduction" show a clear bias towards its use in complexity theory.

Answer 1

Actually, people do commonly use reductions for both purposes: both for proving lower bounds, and for designing algorithms to handle a certain problem.

For instance, it's very common to reduce a problem to linear programming, to a max-flow problem, or to another well-studied problem. This is using reductions for solving problems.

Any particular textbook might focus more one or the other use of reductions. That's a philosophical choice on the part of the author.

Answer 2

I've seen reduction used implicitly. A good example is the problem of finding a maximum spanning tree. In that case, you reduce the problem to the minimum spanning tree problem by multiplying all edge weights by -1, then apply Prim's or Kruskal's algorithm to the new graph.

In this case, reduction was used to "rephrase" the problem in a slightly different way to make it more amenable to an easy solution as opposed to showing that it falls in a particular complexity class.

Answer 3

The need to define reduction formally arises only when defining classes of hard problems. Consider polynomial time reducibility as an example. The same notion is used for both "positive" and "negative" purposes:

• If a problem $A$ can be solved in polynomial time and there is a polynomial time reduction from problem $B$ to problem $A$, then $B$ can also be solved in polynomial time.

• Problem $A$ is NP-hard by definition if there is a polynomial time reduction from any problem $B$ in NP to the problem $A$.

In the first example, there is no need to define reduction formally. We just use the reduction. In the second example, we have to define reduction formally – otherwise we cannot define NP-hardness.

Reductions are used commonly for algorithms. A good example is the paradigm of linear programming. Whenever we use linear programming in an algorithm, we are in effect giving a reduction from our problem to linear programming (not necessarily a many-one reduction, though). Since linear programming can be solved efficiently (in practice and theoretically), the original problem can be solved efficiently.