Reducibility Among Combinatorial Problems Export

@incollection{karp, 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.}, author = {Karp, R. M.}, booktitle = {Complexity of Computer Computations}, citeulike-article-id = {3082225}, editor = {Miller, R. E. and Thatcher, J. W.}, keywords = {complexity, file-import-08-08-04}, pages = {85--103}, posted-at = {2008-08-04 21:01:04}, priority = {1}, publisher = {Plenum Press}, title = {Reducibility Among Combinatorial Problems}, year = {1972} }

TY - CHAP ID - karp L3 - citeulike-article-id:3082225 N2 - 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. EP - 103 TI - Reducibility Among Combinatorial Problems PB - Plenum Press T2 - Complexity of Computer Computations SP - 85 KW - complexity KW - file-import-08-08-04 AU - Karp, RM A2 - Miller, RE A2 - Thatcher, JW PY - 1972/// ER -