1
$\begingroup$

Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$?

I've been learning about NP-Hardness recently and seems that the answer is no. Whenever we show $ A \leq_p B$ its also said that $B$ must therefore be at least as hard as $A$. If this is always the case then is reducing a problem into another only useful for proving NP-Hardness/NP-Completeness? Is there no way to leverage reductions to find an easier problem to solve than the one you originally start out with?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Roughly speaking, no. One way to solve A is by using the method for solving B combined with the reduction from A to B. So if that reduction is efficient, then solving A can't be too much harder than solving B.

If I'm pedantic, yes, B might be a little bit easier to solve than A. If the reduction is very expensive (takes a long time, or significantly increases the size of the problem instance), then B might be a lot easier to solve than A. Normally in study of NP-completeness we address this by requiring the reduction to run in polynomial time, and we ignore any differences that are at most a polynomial factor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.