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.
All labels observed (3)
| Label | Occurrences |
|---|---|
| Subset Sum problem | 1 |
| Subset sum problem canonical | 1 |
| subset sum problem | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7666076 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Subset sum problem Context triple: [NP-completeness, hasCanonicalProblem, Subset sum problem]
-
A.
A Combinatorial Problem
"A Combinatorial Problem" is a classic mathematical paper by N. G. de Bruijn that introduces and analyzes a fundamental counting problem in combinatorics.
-
B.
Waring's problem
Waring's problem is a famous conjecture in number theory that concerns representing natural numbers as sums of fixed powers of integers and determining how many such powers are needed.
-
C.
Sylvester’s theorem on partitions
Sylvester’s theorem on partitions is a result in number theory that provides a systematic way to count integer partitions subject to certain congruence or restriction conditions, forming part of the foundational work in partition theory.
-
D.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
-
E.
Steiner tree problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Subset sum problem Target entity description: 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.
-
A.
A Combinatorial Problem
"A Combinatorial Problem" is a classic mathematical paper by N. G. de Bruijn that introduces and analyzes a fundamental counting problem in combinatorics.
-
B.
Waring's problem
Waring's problem is a famous conjecture in number theory that concerns representing natural numbers as sums of fixed powers of integers and determining how many such powers are needed.
-
C.
Sylvester’s theorem on partitions
Sylvester’s theorem on partitions is a result in number theory that provides a systematic way to count integer partitions subject to certain congruence or restriction conditions, forming part of the foundational work in partition theory.
-
D.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
-
E.
Steiner tree problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
- F. None of above. chosen
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 ⓘ |
| output | yes or no ⓘ |
| parameterizedBy |
number of elements
ⓘ
target sum ⓘ |
| pseudoPolynomialTime | true ⓘ |
| reductionFrom |
3-SAT
ⓘ
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 ⓘ
linked to:
general knapsack cryptosystem
|
| verificationProperty | given a subset, its sum can be checked in polynomial time ⓘ |
| yearCharacterizedAsNPComplete | 1972 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Subset sum problem Description of subject: 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.
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Subset sum problem
subject linked to:
"Reducibility Among Combinatorial Problems" (1972)
linked to: Subset sum problem