Is Subset Sum problem is NPComplete but we know subset sum problem can calculated by dynamic Programing in P time ?
Explain in easy Way with example it would be great
I was reading from book Algorithm Design By Kleinberg and Tardos Proof coudnt understand
Proof We first show that Subset Sum is in ~f{P. Given natural numbers val ..... van, and a target W, a certificate that there is a solution would be the subset wi~ ..... vaik that is purported to add up to W. In polynomial time, we can compute the sum of these numbers and verify that it is equal to W. We now reduce a known NP-complete problem to Subset Sum. Since we are seeking a set that adds up to exactly a given quantity (as opposed to being bounded above or below by this quantity), we look for a combinatorial problem that is based on meeting an exact bound. The B-Dimensional Matching Problem is a natural choice; we show that B-Dimensional Matching 1, vat ---- di-1 ÷ dn+j-1 ÷ d 2n+k-1. Note how taking the union of triples almost corresponds to integer addition: The ls fill in the places where there is an element in any of the sets. But we say almost because addition includes carries: too many ts in the same column will "roll over" and produce a nonzero entry in the next column. This has no analogue in the context of the union operation. In the present situation, we handle this problem by a simple trick. We have only m numbers in all, and each has digits equal to 0 or 1; so if we assume that our numbers arewritten in base d = m + 1, then there will be no carries at all.Thus we construct the following instance of Subset Sum. For each triple t = (xi, Yj, zk) ~ T, we construct a number vat in base m + 1 as defined above. We define V¢ to be the number in base m + 1 with 3n digits, each of which is .--,3n- 1 - equal to 1, that is, V¢ = 2_-,~=0 (m + 1)~. We claim that the set T of triples contains a perfect three-dimensional matching if and only if there is a subset of the numbers {vat} that adds up to V¢. For suppose there is a perfect three-dimensional matching consisting of
