"Reducibility Among Combinatorial Problems" (1972)
E519559
"Reducibility Among Combinatorial Problems" (1972) is a landmark paper by Richard Karp that introduced NP-completeness to a broad audience by showing polynomial-time reductions among 21 classic combinatorial decision problems.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Reducibility Among Combinatorial Problems | 0 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf | scientific paper ⓘ |
| author |
Richard Karp
NERFINISHED
ⓘ
Richard M. Karp NERFINISHED ⓘ |
| basedOn | Cook–Levin theorem NERFINISHED ⓘ |
| citationImpact | highly cited paper in computer science ⓘ |
| contribution |
established NP-completeness of many fundamental problems in graph theory and combinatorics
ⓘ
helped define the standard methodology for proving NP-completeness ⓘ popularized the notion of NP-completeness in computer science ⓘ showed polynomial-time reductions among 21 classic combinatorial decision problems ⓘ |
| establishesNPCompletenessOf |
3-Dimensional Matching problem
NERFINISHED
ⓘ
Chromatic Number problem ⓘ Clique problem ⓘ Exact Cover by 3-Sets problem NERFINISHED ⓘ Exact Cover problem NERFINISHED ⓘ Feedback Vertex Set problem NERFINISHED ⓘ Hamiltonian Cycle problem NERFINISHED ⓘ Hitting Set problem NERFINISHED ⓘ Job Sequencing problem (NP-complete variant) NERFINISHED ⓘ Knapsack problem NERFINISHED ⓘ Node Cover problem ⓘ Partition problem ⓘ Satisfiability problem ⓘ Set Covering problem NERFINISHED ⓘ Set Packing problem NERFINISHED ⓘ Steiner Tree problem (decision version) NERFINISHED ⓘ Subset Sum problem NERFINISHED ⓘ Traveling Salesman problem (decision version) NERFINISHED ⓘ Vertex Cover problem ⓘ |
| field |
computational complexity theory
ⓘ
computer science ⓘ theoretical computer science ⓘ |
| influenced |
algorithm design and analysis
ⓘ
complexity-theoretic classification of combinatorial problems ⓘ development of NP-completeness theory ⓘ |
| introducedConcept | systematic use of polynomial-time many-one reductions among combinatorial problems ⓘ |
| language | English ⓘ |
| publicationYear | 1972 ⓘ |
| publishedIn | Complexity of Computer Computations NERFINISHED ⓘ |
| publisher | Plenum Press NERFINISHED ⓘ |
| status | landmark paper in computational complexity theory ⓘ |
| topic |
NP-complete problems
ⓘ
NP-completeness ⓘ combinatorial decision problems ⓘ polynomial-time reductions ⓘ |
| usesConcept |
decision problem
ⓘ
many-one reduction ⓘ nondeterministic polynomial time ⓘ polynomial-time computable reduction ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.