Premium
On the Computational Complexity of Combinatorial Problems
Author(s) -
Karp R. M.
Publication year - 1975
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1975.5.1.45
Subject(s) - mathematics , time complexity , computational complexity theory , combinatorial optimization , class (philosophy) , polynomial , combinatorics , discrete mathematics , computer science , mathematical optimization , algorithm , artificial intelligence , mathematical analysis
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.