Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Subset sum problem
Summary
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:
The variant in which all inputs are positive.
The variant in which inputs may be positive or negative, and . For example, given the set , the answer is yes because the subset sums to zero.
The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., . This special case of SSP is known as the partition problem.
SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice.
SSP is a special case of the knapsack problem and of the multiple subset sum problem.
The run-time complexity of SSP depends on two parameters:
the number of input integers. If n is a small fixed number, then an exhaustive search for the solution is practical.
the precision of the problem, stated as the number of binary place values that it takes to state the problem. If L is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.
As both n and L grow large, SSP is NP-hard. The complexity of the best known algorithms is exponential in the smaller of the two parameters n and L. The problem is NP-hard even when all input integers are positive (and the target-sum T is a part of the input). This can be proved by a direct reduction from 3SAT. It can also be proved by reduction from 3-dimensional matching (3DM):
We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has n vertices. There are m edges, where each edge contains exactly one vertex from each of W, X, Y. Denote L := ceiling(log2(m+1)), so that L is larger than the number of bits required to represent the number of edges.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.