|
take subset sum. given a subset of numbers find sum n in that set.
let subset-sum-nm be check to make sure the sum is above the number of indexes, n, times the constant m. make sure the sum is above this too, otherwise reject. if not rejected, run subset-sum.
claim: forevery m, subset-sum-nm is in np-complete.
take an input for subset sum, add m to each index, and n*m to the sum, run on subset-sum-nm. this is a polynomial time transformation.
there are infinitely many problems in np-complete!
|
