Subset sum problem
E679894
The subset sum problem is a classic NP-complete decision problem in computer science that asks whether any subset of given integers sums to a specified target value.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
combinatorial optimization problem
ⓘ
computational problem ⓘ decision problem ⓘ |
| asks | whether there exists a subset of the given integers whose sum equals the target value ⓘ |
| belongsTo | NP-complete problems identified by Richard Karp ⓘ |
| complexityClass | NP ⓘ |
| decisionVersionOf | subset sum optimization problem ⓘ |
| definedOver | integers ⓘ |
| difficulty | no known polynomial-time algorithm unless P = NP ⓘ |
| field |
computational complexity theory
ⓘ
computer science ⓘ cryptography ⓘ theoretical computer science ⓘ |
| hasAlgorithm |
backtracking algorithm
ⓘ
branch-and-bound algorithm ⓘ dynamic programming algorithm ⓘ meet-in-the-middle algorithm ⓘ pseudo-polynomial time algorithm for bounded target ⓘ |
| hasApproximation | fully polynomial-time approximation scheme for optimization version ⓘ |
| hasEncoding | binary encoding of integers ⓘ |
| hasVariant |
bounded subset sum problem
ⓘ
optimization version of subset sum ⓘ subset sum counting problem ⓘ subset sum over arbitrary integers ⓘ subset sum over non-negative integers ⓘ unbounded subset sum problem ⓘ |
| input |
finite set of integers
ⓘ
target integer value ⓘ |
| isWeaklyNPComplete | true ⓘ |
| listedIn | Karp's 21 NP-complete problems NERFINISHED ⓘ |
| output | yes or no ⓘ |
| parameterizedBy |
number of elements
ⓘ
target sum ⓘ |
| pseudoPolynomialTime | true ⓘ |
| reductionFrom |
3-SAT
NERFINISHED
ⓘ
partition problem ⓘ |
| reductionTo |
knapsack problem
ⓘ
partition problem ⓘ |
| relatedProblem |
0-1 knapsack problem
ⓘ
exact cover problem ⓘ knapsack problem ⓘ partition problem ⓘ |
| timeComplexity | exponential time for known exact algorithms in the worst case ⓘ |
| typicalInputSizeMeasure | number of integers and bit-length of integers ⓘ |
| usedIn |
complexity theory reductions
ⓘ
cryptographic constructions ⓘ knapsack-based cryptosystems NERFINISHED ⓘ |
| verificationProperty | given a subset, its sum can be checked in polynomial time ⓘ |
| yearCharacterizedAsNPComplete | 1972 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.