complete problems for deterministic polynomial time
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 theorywhether deterministic and nondeterministic polynomial-time-bounded Turing machines are equivalent in powerwas 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 NP 1 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. The main purpose of this paper is to introduce several problems which are complete for P, the class of languages recognizable in deterministic polynomial time. Any such language has the property that if it is recognizable in space log k (), then every language in P is so recognizable. Thus a problem complete for P will serve to differentiate those sets in P which are not recognizable in logarithmic space from those which are, providing such differentiation is possible. A problem of this type was first presented by Cook in [C2], concerning solvable path systems.
completeness polynomial timing reasoning automata algorithm class satisfiability paper language space systems theory power