Is the set-partition problem polynomial time reducible to the subset-sum problem?
-
30-10-2019 - |
题
There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint presentation (slide 12), where it says that the inverse is also true. i.e. the set-partition problem is polynomial time reducible to the subset-sum problem. So far, I have been unable to find any proofs to show the same.
So, my question: How is the set-partition problem polynomial time reducible to the subset-sum problem, or was there an error on the presentation above?
没有正确的解决方案
不隶属于 cs.stackexchange