1
$\begingroup$

Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent problem, but with all $x_i \geq 0$? And if there aren't any, is it possible for there to be such an algorithm?

$\endgroup$
2
$\begingroup$

Both variants are NP-complete, so such a reduction surely exists: the definition of NP-completeness guarantees it.

If you want an explicit reduction, you can reduce one to the other (reduce to 3SAT using Cook's theorem, then reduce 3SAT to the other using its NP-completeness). The resulting reduction will be ugly, though, so I suspect this might not be what you're looking for.

If you want a simple and natural reduction, I'm not sure how to achieve it.

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