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.