A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. Yes, the subset sum problem is NP-complete.
Key classes
- P: decision problems solvable in polynomial time by a deterministic algorithm.
- NP: decision problems whose "yes" answers can be verified in polynomial time given a certificate (equivalently, solvable in polynomial time by a non-deterministic algorithm).
- NP-hard: every problem in NP reduces to it in polynomial time (it is at least as hard as every NP problem).
- NP-complete: a problem that is both in NP and NP-hard. Examples: SAT (proved by Cook's theorem), 3-SAT, vertex cover, clique, Hamiltonian cycle.
If any NP-complete problem could be solved in polynomial time, then P = NP.
Subset sum problem: given a set of positive integers \(S = \{w_1, \dots, w_n\}\) and a target \(M\), is there a subset whose sum is exactly \(M\)?
Proof that it is NP-complete:
- Subset sum ∈ NP. The certificate is the chosen subset. Adding its elements and comparing with \(M\) takes polynomial (linear) time.
- Subset sum is NP-hard. A known NP-complete problem, 3-SAT (or vertex cover), is reduced to it in polynomial time. In the 3-SAT reduction, each variable and each clause becomes a large decimal number whose digit positions encode which variable and clause it belongs to, and the target \(M\) is chosen so that a subset adds up to \(M\) exactly when the formula has a satisfying assignment. The construction has polynomially many numbers with polynomially many digits.
Since it satisfies both conditions, subset sum is NP-complete.
Note: subset sum has a dynamic programming solution in \(O(nM)\) time. This does not contradict NP-completeness, because \(M\) can be exponential in the number of bits used to write it, so the algorithm is only pseudo-polynomial.