Complete problems for deterministic polynomial time
Neil Deaton Jones, William T. Laaser · ACM Symposium on Theory of Computing (STOC) · 1974
The results of Cook and Karp ([K], [C]) aroused considerable interest for at least two reasons. First, the answer to a long-standing open question which had seemed peculiar to automata theory—whether deterministic and nondeterministic polynomial-time-bounded Turing machines are equivalent in power—was seen to be exactly equivalent to determining whether any of several familiar combinatorial problems can be solved by polynomial-time algorithms. Second, the existence of complete problems for NP1 made it possible to replace an entire class of questions by a question about a single representative.Thus all of these combinatorial and automata-theoretic problems were essentially restatements of a single problem, such as: can satisfiability of a propositional formula be decided in polynomial time.
Cited by 41 works. doi:10.1145/800119.803883
Authors
References
- The complexity of theorem-proving procedures
- Formal Languages and Their Relation to Automata
- The Theory of Parsing, Translation, and Compiling
- Symbolic Logic and Mechanical Theorem Proving
- Word problems requiring exponential time(Preliminary Report)
- Space-bounded reducibility among combinatorial problems
- An observation on time-storage trade off
- Path systems and language recognition