refs.bib

@Inbook{Karp1972,
author="Karp, Richard M.",
editor="Miller, Raymond E.
and Thatcher, James W.
and Bohlinger, Jean D.",
title="Reducibility among Combinatorial Problems",
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",
year="1972",
publisher="Springer US",
address="Boston, MA",
pages="85--103",
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.",
isbn="978-1-4684-2001-2",
doi="10.1007/978-1-4684-2001-2_9",
url="https://doi.org/10.1007/978-1-4684-2001-2_9"
}

@inproceedings{10.1145/800157.805047,
author = {Cook, Stephen A.},
title = {The complexity of theorem-proving procedures},
year = {1971},
isbn = {9781450374644},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800157.805047},
doi = {10.1145/800157.805047},
abstract = {It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology. Here “reduced” means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. Other examples are discussed. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.},
booktitle = {Proceedings of the Third Annual ACM Symposium on Theory of Computing},
pages = {151–158},
numpages = {8},
location = {Shaker Heights, Ohio, USA},
series = {STOC '71}
}