Reducibility Among Combinatorial Problems

Richard M. Karp, 1972, Complexity of Computer Computations

About this paperEnglish中文日本語beside Englishbeside 中文beside 日本語

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.

Khả năng quy dẫn giữa các bài toán tổ hợp

Richard M. Karp

Giới thiệu bởi Richard M. Karp

Trong suốt những năm 1960, tôi đã làm việc về các bài toán tối ưu hóa tổ hợp, bao gồm thiết kế mạch logic với Paul Roth, cân bằng dây chuyền lắp ráp và bài toán người bán hàng du lịch với Mike Held. Những kinh nghiệm này khiến tôi nhận thức rằng các bài toán tối ưu hóa rời rạc có vẻ đơn giản có thể chứa những mầm mống của sự bùng nổ tổ hợp. Công trình của Dantzig, Fulkerson, Hoffman, Edmonds, Lawler và các nhà tiên phong khác về luồng trên mạng, ghép cặp và matroid đã giúp tôi làm quen với những thuật toán thanh lịch và hiệu quả đôi khi có thể thực hiện được. Các bài báo của Jack Edmonds và một vài cuộc thảo luận quan trọng với ông đã thu hút sự chú ý của tôi đến sự phân biệt then chốt giữa khả năng giải trong thời gian đa thức và khả năng giải trong thời gian siêu đa thức. Tôi cũng chịu ảnh hưởng bởi sự nhấn mạnh của Jack về các định lý min-max như một công cụ để kiểm chứng nhanh các lời giải tối ưu, điều đã báo trước định nghĩa của Steve Cook về lớp độ phức tạp NP. Một ảnh hưởng khác là đề xuất của George Dantzig rằng quy hoạch nguyên có thể đóng vai trò như một định dạng phổ quát cho các bài toán tối ưu hóa tổ hợp.

Trong suốt những năm 60, tôi đã theo dõi những phát triển trong lý thuyết độ phức tạp tính toán, được khởi xướng bởi Rabin, Blum, Hartmanis, Stearns và những người khác. Vào cuối những năm 60, tôi đã nghiên cứu cuốn sách tuyệt đẹp của Hartley Rogers về lý thuyết hàm đệ quy trong khi giảng dạy một khóa học về chủ đề này tại Polytechnic Institute of Brooklyn. Kinh nghiệm này giúp tôi nhận ra vai trò then chốt của các phép quy dẫn trong lý thuyết hàm đệ quy, và bắt đầu khiến tôi tự hỏi liệu các phép quy dẫn dưới đệ quy có thể đóng một vai trò tương tự trong lý thuyết độ phức tạp hay không, nhưng khi đó tôi vẫn chưa theo đuổi phép tương đồng này.

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 Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.