Reducibility Among Combinatorial Problems.

Karp, R. M. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations.

Type

Book chapter

Intellectual base

Review or monograph

Year

1972

DOI

10.1007/978-1-4684-2001-2_9

ISBN

9781468420036

Link

https://doi.org/10.1007/978-1-4684-2001-2_9

Cited from

mathematics, operations_research

Cited by

3 citations across 3 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.

• 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).

Domain-specific

• Clique (Graph Theory)
  • The decision problem asking whether a clique of size at least \(k\) exists is NP-complete.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:821a1a2b2f97 · see in the full table