Reducibility Among Combinatorial Problems

Richard M. Karp, 1972, Complexity of Computer Computations

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

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.

组合问题之间的可归约性

Richard M. Karp

Richard M. Karp 的引言

整个20世纪60年代，我一直研究组合优化问题，包括与 Paul Roth 合作的逻辑电路设计、与 Mike Held 合作的装配线平衡问题和旅行商问题。这些经历使我意识到，看似简单的离散优化问题可能蕴含着组合爆炸的根源。Dantzig、Fulkerson、Hoffman、Edmonds、Lawler 以及其他先驱者在网络流、匹配和拟阵方面的工作，使我了解了有时可能实现的优雅而高效的算法。Jack Edmonds 的论文以及与他的几次关键讨论，使我注意到多项式时间可解性和超多项式时间可解性之间的关键区别。我还受到 Jack 对极小极大定理的强调所影响，他将其作为快速验证最优解的工具，而这一思想预示了 Steve Cook 对复杂度类 NP 的定义。另一个影响因素是 George Dantzig 提出的建议，即整数规划可以作为组合优化问题的通用形式。

整个60年代，我关注由 Rabin、Blum、Hartmanis、Stearns 以及其他人开创的计算复杂度理论的发展。在60年代末，我在布鲁克林理工学院教授一门关于该主题的课程时，研读了 Hartley Rogers 关于递归函数理论的精彩著作。这段经历使我深刻认识到可归约性在递归函数理论中的关键作用，并开始思考子递归可归约性是否能够在复杂度理论中发挥类似作用，但我当时还没有进一步研究这一类比。

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. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.