Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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,

share|improve this question
1  
Crossposted from Math.SE. –  Peter Taylor May 21 '11 at 8:03
2  
It's a lovely question, but this isn't the place for such a question. –  Frank Shearar May 21 '11 at 17:51
add comment

1 Answer

up vote 12 down vote accepted

Your logic is correct - and what you described is a valid subset-sum algorithm that solves it in O(nt).

However, this type of algorithm is pseudopolynomial, meaning that it is exponential to the number of bits used to represent the input. What that means is, if your t is 1000, then I can make your program 10 times slower by adding another 0 to it (t is now 10000).

So while the algorithm is polynomial to the value of n and t, it is exponential to the size of the input (number of characters, bits, whatever you want to call them, in the input).

And hence, this problem is not in P (unless P = NP or something similar).

Source and further reading

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.