2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Jul 7 '16 at 0:04
  • $\begingroup$ The term "reduction" is used like this in this particular field of complexity theory. That does not create a monopoly for all of CS, let alone the whole world. $\endgroup$ – Raphael Jul 7 '16 at 0:05
  • $\begingroup$ Please take a look at meta.cs.stackexchange.com/q/657/755 $\endgroup$ – D.W. Jul 8 '16 at 15:51
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed. Complexity theory texts may use "positive" reduction to show upper bounds as well, in particular to "standard" forms like linear/integer programming. In algorithms text, I'd expect it to be ubiquitous. $\endgroup$ – Raphael Jul 7 '16 at 6:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your answer is actually my question. Why is reduction used implicitly and only properly defined and formalized in the context of proving hardness. $\endgroup$ – Amir Nasr Jul 8 '16 at 9:22
1
$\begingroup$

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.

$\endgroup$

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.