2
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – Raphael Jan 13 '14 at 16:03
  • $\begingroup$ There's not a complete answer to my question as my question is basically wether my proof valid or not. So I disagree into this not helping me (I don't know if my proof is right) nor other future visitors (who might wonder about this, or a similar problem, which is actually a variant of the classical subset-sum). Of course there's also another part of my question (labeled now as "Extra question") which hasn't been solved at all. $\endgroup$ – Setzer22 Jan 13 '14 at 17:35
  • 1
    $\begingroup$ The extra problem is probably best off with its own question; it's bad to mix two questions that have separate answers. Regarding the main closing reason, did you read the discussions on meta I linked? Your post is a textbook example of questions we don't want. If it's an exercise for a class, grading should be done by your TA; if it's not, you should at least pinpoint places where you are not sure. (If there are none, why ask the question?) $\endgroup$ – Raphael Jan 13 '14 at 19:02