Computer Science Asked by DUO on December 8, 2020

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?

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.

Correct answer by D.W. on December 8, 2020

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP