6
$\begingroup$

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the target (if possible).

But can't this problem be solved in polynomial time by dynamic programming method where we construct a table n X t and take cases like say last number is surely included in output and then the target becomes t- a[n]. In other case, the last number is not included, then the target remains same t but array becomes of size n-1. Hence this way we keep reducing size of problem.

If this approach is correct, isn't the complexity of this n * t, which is polynomial? and so if this belongs to P and also NP-complete (from what I hear) then P=NP.

Surely, I am missing something here. Where is the loophole in this reasoning?

Thanks,

  • 7
    The loophole is that input is smaller than you think. The dynamic programming method is pseudo-polynomial: it's polynomial in the values supplied as input, but the values are exponential in their length when represented in any base greater than 1.2011-05-21
  • 2
    t is exponential in the input size. With k digits of input you can represent numbers up to about 10^k (or 2^k or whatever).2011-05-21
  • 0
    Not to put too fine a point on it, but your argument would also show that trial division is a polynomial-time factorization algorithm. Factoring $n$ by trial division is polynomial in $n$, but not in the length of $n$, which length is $\log n$, and it's the length of $n$ - the length of the input - that counts.2011-05-21
  • 3
    Another issue is that you haven't formulated the problem as a *decision* problem (with a yes/no answer), but NP consists only of decision problems. Perhaps in the actual problem you intend to consider, the output should just be yes or no depending on whether there is such a subset, without needing to return the satisfying instance. This difference sometimes matters, since for example, testing primality is polynomial time, but we don't expect to be able to get factors in polynomial time.2011-05-21
  • 2
    The answering comments above should be posted as answers. This site works much better when answers are posted as answers.2011-05-21

2 Answers 2