Complete problems for deterministic polynomial time

ABSTRACT

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. 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 logk(•), 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.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 3: Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805151]
• 4: Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
• 5: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 6: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 7: Jones, N.D. Space-bounded reducibility among combinatorial problems, To appear. Preliminary version in 7th Princeton Conf. on Information Science and Systems, 547-551 (1973)
• 8: Karp, R.M., Reducibility among combinatorial problems, in "Complexity of Computer Computations", R.E. Miller and J.W. Thatcher, eds., Plenum Press, N. Y. (1972)
• 9: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Theory