The subset sum problem considers a collection of numbers and a number . We want to find a subcollection that sums to . The corresponding language is given
NP-Complete
Info
is NP-complete
A nondeterministic Turing machine a select an arbitrary subset and test if it sums up correctly in polynomial time. Thus .
To show completeness, we reduce from 3SAT. Let be a Boolean formula with variables and clauses . For each variable and clause , add the following numbers to a collection
Write . Note that when summing these numbers together, the total weight on each digit is at most , thus adjacent digits cannot affect each other through carrying. A satisfying assignment corresponds exactly to choosing one of and for a truth assignment of , and padding any clauses with less than three true literals using and . This is a polynomial time reduction, thus is NP-complete.