1
$\begingroup$

I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a constant number? So the decision problem would look like this:

Input: A collection of nonnegative integers A and a nonnegative integer b,

Output: Boolean value indicating whether some subset of the collection sums to 10

Would this still be NP-complete? I don't believe you would be able to reduce every other NP-complete problem to it.

$\endgroup$
5
$\begingroup$

We can throw away all zeroes in $A$. If a subset of $A$ sums to $10$, then this subset contains at most $10$ elements. There are at most $10|A|^{10}$ such non-empty subsets, so we can go over all of them in polynomial time.

$\endgroup$
-3
$\begingroup$

Subset sum problem with only one number is probably not NP-complete, because there is a polynomial algorithm that solves this problem.
If it is NP-complete, then P=NP.

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