So we have two problems:
Problem A: Given a list of positive integers, decide whether the list contains a subset adding to a given number t.
Problem B: Given a list of integers, decide whether the list contains a subset adding to 0.
I have to prove that A can be reduced to B in polynomial time. And a really simple reduction came into mind. Here goes my proof.
So let L be the list of positive integers from the problem A, I just create L' add -t to the it, and pass L' to B, this is the reduction.
To prove this is a reduction, let's see that, L is a positive instance of A if and only if L' is a positive instance of B. Am I doing it right?
So first:
=>) It's just obvious to prove that, given a list of integers which contains a subset adding up to t, this list, along with -t adds up to 0.
<=) Let S be the subset of L' that adds up to 0. Given that, by construction, all integers in L' are positive but one, which is -t, -t must be in S. If S contains the only negative number -t, and S adds up to 0, S{-t}, adds up to t. Then S{-t} is a subset of S{-t} = L that adds up to t.
Question:
Is my proof correct?
Is there any obvious mistake which makes it invalid?
Are there any minor mistakes which could be fixed to "improve" it?
Extra question:
And also, I would like to ask a more generic question. Consider the problem A, but removing the "positive" part, so L can now contain both positive and negative numbers on it. I know A' (the new A) is still reductible to B, because they both belong to the NP-complete problem class. So my other question is:
- How can I reduce A' to B?