@inbook{Karp1972,
    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.},
    Address = {Boston, MA},
    Author = {Karp, Richard M.},
    BookTitle = {Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20--22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department},
    Editor = {Miller, Raymond E. and Thatcher, James W. and Bohlinger, Jean D.},
    File = {Reducibility among Combinatorial Problems - karp1972.pdf},
    ISBN = {978-1-4684-2001-2},
    Pages = {85--103},
    Publisher = {Springer US},
    Title = {Reducibility among Combinatorial Problems},
    URL = {https://doi.org/10.1007/978-1-4684-2001-2\_9},
    Year = {1972},
    bdsk-url-1 = {https://doi.org/10.1007/978-1-4684-2001-2\_9},
    date-added = {2021-07-23 17:39:06 +0200},
    date-modified = {2021-07-23 17:39:06 +0200},
    file-2 = {Reducibility among Combinatorial Problems - karp.pdf},
    doi = {10.1007/978-1-4684-2001-2_9}
}

@inbook{Karp1972, 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.}, Address = {Boston, MA}, Author = {Karp, Richard M.}, BookTitle = {Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20--22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department}, Editor = {Miller, Raymond E. and Thatcher, James W. and Bohlinger, Jean D.}, File = {Reducibility among Combinatorial Problems - karp1972.pdf}, ISBN = {978-1-4684-2001-2}, Pages = {85--103}, Publisher = {Springer US}, Title = {Reducibility among Combinatorial Problems}, URL = {https://doi.org/10.1007/978-1-4684-2001-2_9}, Year = {1972}, bdsk-url-1 = {https://doi.org/10.1007/978-1-4684-2001-2_9}, date-added = {2021-07-23 17:39:06 +0200}, date-modified = {2021-07-23 17:39:06 +0200}, file-2 = {Reducibility among Combinatorial Problems - karp.pdf}, doi = {10.1007/978-1-4684-2001-2_9} }