Source / pinned edition
Reducibility Among Combinatorial Problems
Source of package karp.combinatorial_reductions_1972 · in Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103
- work
- urn:doctrine:cs:karp-1972#KARP_1972
- number
- in Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103
- kind
- urn:doctrine:cs:karp-1972#treatise
KARP_1972_PLENUM
- edition
- urn:doctrine:cs:karp-1972#KARP_1972_PLENUM
- language
- en
- officiality
- official
- materialisation
- PINNED_UNOFFICIAL_COPY
- life cycle
- adopted: 1972-01-01
Publications
| URI | Type | documentHash | Retrieved |
|---|---|---|---|
| https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9 | text/plain; charset=utf-8 | sha256:f8af5ec4bc6df845b0ac99b6a79f24648ba3ae64260afcd3695bd1f306a8c13a | 2026-09-17T00:00:00Z |
Fragments — 3
2010-introduction · defn · referenced by: 15
en · official · sha256:23ef68eeab9ecc356cfbb1aaf6f7fa7d4b69044cba990cc7d836970d8340c4fc
Cook's 1971 paper [1], in which he defined the class NP and showed that propositional satisfiability was an NP-complete problem, brought together for me the two strands of complexity theory and combinatorial optimization. It was immediately apparent to me that many familiar combinatorial problems were likely to have the same universal role as satisfiability.Referencing norms: 3sat-reduces-to-clique, CliqueChecker, CliqueLanguage, KarpClaim, ThreeSatLanguage, VertexCoverChecker, VertexCoverLanguage, clique-checker-checks, clique-checker-poly-certificate, clique-checker-poly-time, clique-reduces-to-vertex-cover, sat-reduces-to-3sat, vertex-cover-checker-checks, vertex-cover-checker-poly-certificate, vertex-cover-checker-poly-time
2010-introduction.reductions · defn · referenced by: 4
en · official · sha256:d725c160777f79bcbf05e99366dc6c5520051ffa8e7976ede6c767ae4dddfc40
Most of them were easy to find, but I failed to prove the NP-completeness of the undirected hamiltonian circuit problem; that reduction was provided independently by Lawler and Tarjan. I was also frustrated by my inability to classify linear programming, graph isomorphism and primality.Referencing norms: HamiltonianCircuitLanguage, KarpProof, karp-proves, vertex-cover-reduces-to-hamiltonian-circuit
title · defn · referenced by: 1
en · official · sha256:7f1a521455401fefda33ba07c58930ed652478171ee4be4f6780b5573a4aa09b
Reducibility Among Combinatorial Problems
Richard M. Karp
University of California, BerkeleyReferencing norms: KarpSource
The hash beside the text is the sha256 of its exact bytes. It is the check that the text shown matches the one pinned in the package: a divergence fails the oracle’s static analysis.