Reducibility Among Combinatorial Problems

Richard M. Karp, 1972, Complexity of Computer Computations

About this paperTiếng Việt中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

English
日本語

Chapter 8 Reducibility Among Combinatorial Problems

Richard M. Karp

Introduction by Richard M. Karp

Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems.

Throughout the ’60s I followed developments in computational complexity theory, pioneered by Rabin, Blum, Hartmanis, Stearns and others. In the late ’60s I studied Hartley Rogers’ beautiful book on recursive function theory while teaching a course on the subject at the Polytechnic Institute of Brooklyn. This experience brought home to me the key role of reducibilities in recursive function theory, and started me wondering whether subrecursive reducibilities could play a similar role in complexity theory, but I did not yet pursue the analogy.

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. I enjoyed constructing the polynomial-time reductions that verified this intuition. 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.

As I recall I first presented my results at an informal seminar at Don Knuth’s home, and a few months later, in April 1972, I exposed the work more broadly at an IBM symposium. In the next couple of years many results more refined than my own were added to the accumulation of NP-completeness proofs, and later the Garey-Johnson book [2] presented the concepts to a wide audience.

Heuristic algorithms often find near-optimal solutions to NP-hard optimization problems. For some time in the mid-1970s I tried to explain this phenomenon by departing from worst-case analysis, and instead analyzing the performance of simple heuristics on instances drawn from simple probability distributions. This work was technically successful but gained limited traction, because there was no way to show that the problem instances drawn from these probability distributions are representative of those arising in practice. The surprising success of many heuristics remains a mystery.

組合せ問題間の還元可能性

Richard M. Karp

Richard M. Karpによる序論

1960年代を通じて、Paul Rothと論理回路設計を、Mike Heldと組立ラインのバランシングおよび巡回セールスマン問題を含む、組合せ最適化問題に取り組んだ。これらの経験から、一見単純な離散最適化問題が、組合せ爆発の種を内包し得ることを認識した。Dantzig、Fulkerson、Hoffman、Edmonds、Lawlerおよびその他の先駆者たちによるネットワークフロー、マッチング、マトロイドの研究を通じて、ときに可能であった洗練された効率的なアルゴリズムに触れた。Jack Edmondsの論文と彼とのいくつかの重要な議論によって、多項式時間での解決可能性と超多項式時間での解決可能性の間にある決定的な相違に注意を向けるようになった。また、最適解を迅速に検証する手段としてのmin-max定理を重視するJackの姿勢にも影響を受けた。これは、Steve Cookによる計算量クラスNPの定義を予示するものであった。もう一つの影響は、整数計画法が組合せ最適化問題のための普遍的な形式として役立ち得るというGeorge Dantzigの提案であった。

1960年代を通じて、Rabin、Blum、Hartmanis、Stearnsらが先導した計算量理論の発展を追っていた。1960年代後半には、ブルックリン工科大学で再帰関数理論の講義を担当しながら、Hartley Rogersの美しい著書を学んだ。この経験によって、再帰関数理論における還元可能性が果たす中心的な役割を深く認識し、部分再帰的還元可能性が計算量理論においても同様の役割を果たし得るのではないかと考え始めたが、当時はまだその類推を追究していなかった。

1 INTRODUCTION

This section is missing here.

2 THE CLASS $P$

This section is missing here.

3 NONDETERMINISTIC ALGORITHMS AND COOK'S THEOREM

This section is missing here.

4 COMPLETE PROBLEMS

This section is missing here.

5 NODE COVER

This section is missing here.

6 SET COVERING

This section is missing here.

7 FEEDBACK NODE SET

This section is missing here.

8 FEEDBACK ARC SET

This section is missing here.

9 DIRECTED HAMILTON CIRCUIT

This section is missing here.

10 UNDIRECTED HAMILTON CIRCUIT

This section is missing here.

11 SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE

This section is missing here.

12 CHROMATIC NUMBER

This section is missing here.

13 CLIQUE COVER

This section is missing here.

14 EXACT COVER

This section is missing here.

15 HITTING SET

This section is missing here.

16 STEINER TREE

This section is missing here.

17 3-DIMENSIONAL MATCHING

This section is missing here.

18 KNAPSACK

This section is missing here.

19 JOB SEQUENCING

This section is missing here.

20 PARTITION

This section is missing here.

21 MAX CUT

This section is missing here.

Appendix I

This section is missing here.

References

  1. 1. S.A. Cook, *The complexity of theorem proving procedures*, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. 2. M.R. Garey and D.S. Johnson, *Computers and Intractability: A Guide to the Theory of NP-Completeness*, W.H. Freeman & Co., 1979.
  2. 8 Reducibility Among Combinatorial Problems
  3. The following article originally appeared as:
  4. R.M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.), Plenum Press, 1972, pp. 85–103.
  5. Copyright © 1972 Plenum Press.
  6. Reprinted by permission from Kluwer Academic Publishers.
  7. Richard M. Karp University of California at Berkeley
  8. Abstract: A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. 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.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.