Skip to main content

Questions about the NP-complete problem Subset Sum.

Subset Sum is one of the canonical NP-complete problem. Given a set $S$ of positive integers and a target $B$, is there a subset of $S$ summing to $B$? An optimization variant asks for the subset of $S$ whose sums is closest to $B$.

Subset Sum is NP-hard if the integers in $S$ are encoded in binary (i.e., in the usual way), but if they are encoded in unary (that is, $n$ is encoded as $1^n$, the string consisting of $n$ many ones), a dynamic programming algorithm solves Subset Sum in polynomial time.

The trivial $2^n$ algorithm (where $n = |S|$) for solving Subset Sum can be improved to $c^n$ for some $c < 2$. Assuming SETH, there is no $2^{o(n)}$ algorithm. The best value of $c$ (conditional on SETH or similar hardness assumptions) is currently unknown.