On the Computational Complexity of Combinatorial Problems

Networks - Tập 5 Số 1 - Trang 45-68 - 1975
Richard M. Karp1
1University of California, Berkeley, California

Tóm tắt

A large class of classical combinatorial problems, including most of the difficult problems in the literature of network flows and computational graph theory, are shown to be equivalent, in the sense that either all or none of them can be solved in polynomial time. Moreover, they are solvable in polynomial time if and only if every problem solvable by a polynomial‐depth backtrack search is also solvable by a polynomial‐time algorithm. The technique of deriving these results through problem transformations is explained, and some comments are made as to the probable effect of these results on research in the field of combinatorial algorithms.

Từ khóa


Tài liệu tham khảo

10.1073/pnas.43.9.842

10.1287/mnsc.17.5.354

Chvatal V. personal communication 1973.

Cobham A., 1965, Logic, Methodology and Philosophy of Science

10.1145/321623.321625

Cook S. A., 1971, The Complexity of Theorem-Proving Procedures,, Proc. of the Third ACM Symposium on Theory of Computing, 151

10.2307/1905292

Edmonds, 1965, J., “Paths, Trees and Flowers,” Canad, J. Math., 17, 449

Edmonds J., 1970, Combinatorial Structures and Their Applications, 89

Erdös P., 1974, Probabilistic Methods in Combinatorics

Fagin R., 1974, Complexity of Computation

10.1145/321420.321422

10.1515/9781400875184

Gabow H., 1972, Technical Report

Garey M. R., 1972, Worst-Case Analysis of Memory Allocation Algorithms,, Proc. of the Fourth ACM Symposium on Theory of Computing, 143

Garey M. R., 1974, Complexity Results for Multiprocessor Scheduling Under Resource Constraints,, Bell Telephone Laboratories

Garey M. R., 1974, Some Simplified NP-Complete Problems,, Proc. of the Sixth ACM Symposium on Theory of Computing, 47

10.1137/0202019

Hoperoft J. E., 1969, Formal Languages and Their Relation to Automata

Ibarra O., 1974, Technical Report

10.1007/978-1-4684-2001-2_9

10.1137/0204023

Klee V., 1970, Mathematical Note No. 643

D. E. Knuth 1974

Kou L., Polynomial Complete Consecutive Information Retrieval Problems,, Siam. J. Comp.

Ladner R., 1974, Comparison of Polynomial-Time Reducibilities,, PPOC. of the Sixth ACM Symposium on Theory of Computing, 110

Lawler E. L., 1974, Combinatorial Optimization: Networks and Matroids, Holt

Lin S., 1975, Heuristic Programming as an Aid to Network Design,, Proc. of the Symposium on Large-Scale Networks, Networks, 5, 33

Reiter R. personal communication 1971.

Rivest R. personal communication 1974.

Rosencrantz D. J., 1974, Approximation Algorithms for the Traveling-Salesperson Problem,, Proc. of the Fifteenth IEEE Switching and Automata Theory Symposium

Schaefer T. personal communication 1974.

10.1145/800009.808055

10.1007/BF01580132

Thông tin
Thông tin xuất bản

Networks

Tập 5 Số 1

45-68

Thông tin tác giả