Reducibility Among Combinatorial Problems.¶
Karp, R. M. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations.
Cited by¶
6 citations across 6 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Integer Linear Programming (ILP)
- Complexity-management costs include: NP-hardness in the worst case — Karp (1972) placed integer programming squarely within his catalog of NP-complete problems, fixing its theoretical hardness baseline.
This sourceEstablishes NP-completeness of 21 combinatorial problems including 0-1 integer programming; fixes the worst-case hardness baseline for ILP.
Supported in partVerified against the publisher's abstract
Karp's abstract establishes the polynomial-equivalence framework that fixes a worst-case hardness baseline for a large class of combinatorial problems, but it never names integer programming or a catalog of NP-complete problems.
“We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.”
- Complexity-management costs include: NP-hardness in the worst case — Karp (1972) placed integer programming squarely within his catalog of NP-complete problems, fixing its theoretical hardness baseline.
- Verifier-Prover Asymmetry
- The qualitative gap is therefore the textbook difference between exponential and polynomial — a difference in kind, in growth rate, not a constant factor — and SAT being NP-complete means this same gap is shared by thousands of other problems (graph colouring, the travelling-salesman decision problem, scheduling) under polynomial reductions.
This sourcePolynomial reductions establishing that SAT's gap is shared by graph coloring, TSP-decision, and scheduling (NP-completeness).
Supported in partVerified against the publisher's abstract
Karp's abstract asserts that a large class of classic combinatorial problems are mutually polynomial-reduction equivalent, but it names SAT, graph colouring, TSP-decision or scheduling nowhere and does not say 'thousands'.
“We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.”
- The qualitative gap is therefore the textbook difference between exponential and polynomial — a difference in kind, in growth rate, not a constant factor — and SAT being NP-complete means this same gap is shared by thousands of other problems (graph colouring, the travelling-salesman decision problem, scheduling) under polynomial reductions.
Domain-specific¶
- Clique (Graph Theory)
- Feasible Region
- When it is non-convex (as in integer programmes, mixed-integer programmes, and many engineering design problems), the geometry is far more complex — the set of feasible points may be disconnected, its interior may be empty (as in pure integer programmes, where the feasible region is a discrete lattice), and finding even a feasible solution, let alone an optimal one, can be NP-hard
This sourceKarp's equivalence result that a large number of classic combinatorial problems of covering, matching, packing, routing, assignment and sequencing share the same polynomial-time complexity.
Supported in partVerified against a saved copy of the source
“We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.”
- When it is non-convex (as in integer programmes, mixed-integer programmes, and many engineering design problems), the geometry is far more complex — the set of feasible points may be disconnected, its interior may be empty (as in pure integer programmes, where the feasible region is a discrete lattice), and finding even a feasible solution, let alone an optimal one, can be NP-hard
Mechanisms¶
- Bipartite Coverage Matrix
- Note, too, that choosing the smallest set of sources that still covers every target is the classic set-cover problem
This sourceFormulates set cover as selecting a smallest family of sets whose union covers every target element.
- Note, too, that choosing the smallest set of sources that still covers every target is the classic set-cover problem
- Reduction Boundary Map
- The lineage of many-one reduction and completeness
This sourceDefines a polynomial-time reduction by a transformation that preserves membership equivalence: an instance is a yes-instance of one problem if and only if its image is a yes-instance of the other.
- The lineage of many-one reduction and completeness
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 3 of 6 citations: 3 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:821a1a2b2f97 · see in the full table