1971/01/01 by Stephen Cook · 6,189 citations
Computer Science · Mathematics · #Algorithm #Bounded function #Computability, Logic, AI Algorithms #Computation #Computer science #Conjunctive normal form #Constraint satisfaction problem #Decision problem #Discrete mathematics #Machine Learning and Algorithms #Mathematics #NP #Nondeterministic algorithm #Oracle #Predicate (mathematical logic) #Propositional calculus #Time complexity #Time hierarchy theorem #Turing machine #Universal Turing machine #semigroups and automata theory
paper · pdf · doi:10.1145/800157.805047
openalex publication_date 1971/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.