3
$\begingroup$

Can I always increase the complexity of a problem via polynomial reduction? (in which case 'reduction' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest element in an array, by iterating through and making comparisons with the smallest value found thus far), what would be a corresponding problem in NP-complete (obtained via polynomial reduction)? Or, would it be possible to polynomially reduce a constant time (worst case) algorithm into a polynomial time algorithm (basically performing unnecessary executions for all n of the input for nothing)?

As a side request, I'm looking for a basic reference that deals with how one problem (in P or NP-complete) can be reduced (in polynomial time) to a problem in (P or NP-complete). Most of the things I found online are beyond scope or vague. I'm looking for an easy way to figure out whether a certain Problem A (in P or NP-complete) can be polynomially reduced to a Problem B (in P or NP-complete).

$\endgroup$
  • 5
    $\begingroup$ the aim of a polynomial-time reduction is not to increase the complexity of a problem, but instead to show that an algorithm that solves a problem B can be efficiently used to solve another problem A (and we say that A is polynomial-time reducible to B). $\endgroup$ – Vor Oct 8 '12 at 21:52
7
$\begingroup$

As pointed out by @Vor the point of polynomial-time reductions is to show that if have a reduction from A to B and an algorithm to solve a problem B then you can use it to efficiently (i.e. in polynomial time) solve the problem A. Note that efficiently does not mean optimally, when you reductions, your solutions will not be better than the class your use for reductions (i.e. if you use a polytime reduction to reduce to a constant time language, you still have just a polytime algorithm).

I think what you are getting confused about is that reductions can be used to show that a problem is easy or that it is hard. In this case, they are used in two different ways. Suppose you have some problem X, and

  1. you think it is easy (i.e. doable in polynomial time). In that case you find your favorite polynomial time problem B (say linear programming) and reduce X to B. Now you have an efficient algorithm for X: run the reduction and then run a polytime LP-solver. On the other hand,

  2. you think X is hard (i.e. probably not doable in polynomial time). In that case you find your favorite NP-complete problem A (say 3-SAT) and reduce A to X. Now if you had an efficient algorithm for X, you would be able to solve A in polynomial time (reduction, then X). Since we suspect that A cannot be solved in polynomial time, this means we have a contradiction, so you cannot have an efficient algorithm for X.

There is no general rule for deciding if a given problem is in P or NP-complete, but we have a list of rules of thumb to help you.

$\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.