NP-completeness

i’ve seen problems which are stated under NP-comleteness like “Subset Sum Problem”. But there is a O(sum*n) solution to this problem using Dynamic Programming paradigm. Then why do we categorize the problem under NP-Complete ? , Am I misunderstanding something… ?
Thanks in advance… A link to any tutorial in which exhaustive analysis of NP-P concept is done, would be really helpful, Thanks in Advance…

O(sum*N) is exponential complexity or pseudo polynomial one at least.

In Computer Science complexity is measured by the number of bits in input, number of bits in sum is M M = log(sum) so the true complexity is O(2^M * N) which is clearly exponential.

Now if you had an algorithms which would solve the problem in something like O(N * log(sum)) then that would be a polynomial time algorithm.

source : http://en.wikipedia.org/wiki/Pseudo-polynomial_time

This is a just a brief explanation you can read about complexity theory in a lot of different sources.

EDIT According to the wikipedia (above article) your problem is in the class of so-called “weakly NP-complete”.

1 Like

thanks @c0d3junki3 ,got it! :slight_smile: , was missing the point of the sum value being the reason for the approach being, non-polynomial…

//