Источник / закреплённая редакция
Reducibility Among Combinatorial Problems
Источник пакета karp.combinatorial_reductions_1972 · in Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103
- work
- urn:doctrine:cs:karp-1972#KARP_1972
- номер
- in Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103
- вид
- urn:doctrine:cs:karp-1972#treatise
KARP_1972_PLENUM
- edition
- urn:doctrine:cs:karp-1972#KARP_1972_PLENUM
- язык
- en
- официальность
- official
- материализация
- PINNED_UNOFFICIAL_COPY
- жизненный цикл
- adopted: 1972-01-01
Публикации
| URI | Тип | documentHash | Получено |
|---|---|---|---|
| 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 |
Фрагменты — 3
2010-introduction · defn · на него ссылаются: 15
en · official · sha256:23ef68eeab9ecc356cfbb1aaf6f7fa7d4b69044cba990cc7d836970d8340c4fcEN
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.Ссылаются нормы: 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 · на него ссылаются: 4
en · official · sha256:d725c160777f79bcbf05e99366dc6c5520051ffa8e7976ede6c767ae4dddfc40EN
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.Ссылаются нормы: HamiltonianCircuitLanguage, KarpProof, karp-proves, vertex-cover-reduces-to-hamiltonian-circuit
title · defn · на него ссылаются: 1
en · official · sha256:7f1a521455401fefda33ba07c58930ed652478171ee4be4f6780b5573a4aa09bEN
Reducibility Among Combinatorial Problems
Richard M. Karp
University of California, BerkeleyСсылаются нормы: KarpSource
Хэш рядом с текстом — sha256 его точных байтов. Он и есть проверка того, что показанный текст совпадает с закреплённым в пакете: расхождение роняет статику оракула.