How to show that some problem is in NP and that it's NP-complete

Question

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.

---

Answer 1

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