0
$\begingroup$

I need some help with the following question:

Recall the subset sum problem, which is known to be NP-complete:

"Given a finite set of natural numbers and a number $n$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."

We consider the great subset sum problem:

"Given a finite set of natural numbers adding up to $N$ and a number $n > N/2$, decide whether a subset of the given set exists such that the numbers in that subset sum up to $n$."

a. Show that the great subset sum problem is in NP by giving the notion of certificate and arguing that the certificate can be checked in polynomial time.

b. Show that the great subset sub problem is NP-complete.

(Hint: extend the set by adding one large number.)

This was my "proof" but I think it lacks details and I feel it's wrong because I didn't use the hint for part B. Can someone tell me if did something wrong? But please, don't get use too many technical terms as we mainly use text and I might not understand your explanation.


a) A certificate for the great subset sum problem is a subset of the given set of natural numbers.

Certificate checking is done by adding up the numbers in the subset and comparing the result to the number n without forgetting the extra requirement that n > $N/2$.

Clearly, if m is the size of the original set of numbers (i.e., the size of the input), then the verification requires at most $m-1$ additions, one comparison, and final checking step, so it can be done in $O(m)$.

$O(m)$ because of the following: Adding 2 numbers takes O(1), you have to do that m-1 times. Then do one computation which also takes O(1) and finally do one comparison which also takes O(1), so in total that's O(m).

b) From the first part of the exercise it already follows that the great subset-sum problem is in NP.

To show that the great subset-sum problem is NP-complete, it remains to prove that it is NP-hard. The latter we can do by showing a polynomial-time reduction from the subset sum problem to the great subset sum problem.

Let S be a set of natural numbers and let n be a natural number. Let $S^\prime$ be obtained from S by dividing every number in S by 2; clearly, $S^\prime$ can be obtained by an algorithm whose running time is linear in the size of S. Note that S has a subset such that the numbers in that subset add up to n if, and only if, $S^\prime$ has a subset such that the numbers in that subset add up to n where n > $N/2$.

So, we have now presented a polynomial-time reduction from the subset-sum problem to the great subset-sum problem. Since the subset sum problem is NP-hard, it follows that the great subset sum problem is NP-hard too.


$\endgroup$
  • $\begingroup$ If you divide all numbers by 2, you also have to divide the target by 2. So you didn't gain anything. $\endgroup$ – Yuval Filmus Jan 11 '18 at 10:33
  • $\begingroup$ @YuvalFilmus correct me if i understood you wrong, so i just have to divide n by two and then it's correct? $\endgroup$ – Does it matter Jan 11 '18 at 10:40
  • $\begingroup$ Suppose that the numbers are 2,4,6 and the target is 2, which is smaller than 12/2. You suggest dividing everything by 2: the numbers are 1,2,3 and the target is 1. Unfortunately, 1 is still smaller than 6/2. $\endgroup$ – Yuval Filmus Jan 11 '18 at 10:41
  • 1
    $\begingroup$ That's for you to answer. The only way to understand a mathematical topic is to solve questions. $\endgroup$ – Yuval Filmus Jan 11 '18 at 10:43
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Jan 11 '18 at 15:54
1
$\begingroup$

When performing a reduction it is important to keep in mind exactly what you are doing. In particular you are trying to reduce from a known hard problem (here subset sum, $\mathsf{SS}$) to your problem (here great subset sum, $\mathsf{GSS}$) such that yes-instances of the hard problem map to yes-instances of your problem and no-instances map to no-instances.

As mentioned in the comments, if you simply divide each number in $S$ by two (and also divide $n$ by two) you do not get an instance of $\mathsf{GSS}$; it might not be the case that $\frac{n}{2} \geq \frac{N}{2}$.

Please think about the problem a bit more before looking at the solution below.

Let our $\mathsf{SS}$ instance be $S = \{s_1, ..., s_k\}$ with $\sum_{s_i \in S} s_i = N$ and target $n$. We construct the following $\mathsf{GSS}$ instance: $S' = \{s_1, ..., s_k, N\}$ with target $n' = N + n$. Observe that this is a $\mathsf{GSS}$ instance since $n' \geq \frac{1}{2}\sum_{s \in S'} s = N$. It remains to show that yes-instances map to yes-instances and no-instances map to no-instances. If some subset $A \subseteq S$ adds up to $n$ then $A \cup \{N\}$ adds up to $N + n$. If not then no subset of $S'$ adds up to $n'$ since $n' > N$ so this subset must contain $\{N\}$ and a subset of $S$ which adds up to $n$.

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