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! 
, was missing the point of the sum value being the reason for the approach being, non-polynomial…