A new recursion-theoretic characterization of the polytime functions (extended abstract)

ABSTRACT

We give a recursion-theoretic characterization of FP which describes polynomial time computation independently of any externally imposed resource bounds. In particular, this syntactic characterization avoids the explicit size bounds on recursion (and the initial function 2|x|.|y|) of Cobham.

REFERENCES

• Al: B. Allen, "Arithmetizing Uniform NC", Annals of Pure and Applied Logic, v. 53, 1991, North Holland.
• Be: S. Bellantoni, "Using Safe Recursion to Delineate Computational Complexity", PhD Thesis, University of Toronto, 1992 (to appear).
• BC: Stephen Bellantoni , Stephen Cook, A new recursion-theoretic characterization of the polytime functions, Computational Complexity, v.2 n.2, p.97-110, 1992 [doi>10.1007/BF01201998]
• Bl: S. Bloch, "Functional Characterizations of Uniform Log-depth and Polylog-depth Circuit Families", manuscript, Dept. Mathematics, University of California at San Diego, 1992.
• B: S. Buss, "Bounded Arithmetic", Ph.D. Dissertation, Princeton University, 1985; reprinted Bibliopolis, Naples, 1986.
• Cob: A. Cobham, "The intrinsic computational difficulty of functions". In Y. Bar-Hillel ed., Proc. of the 196# International Congress for Logic, Methodology, and the Philosophy of Science, p. 24-30. North Holland, Amsterdam, 1964.
• C: Stephen A. Cook, Feasibly constructive proofs and the propositional calculus (Preliminary Version), Proceedings of seventh annual ACM symposium on Theory of computing, p.83-97, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803756]
• C2: S. Cook, "Computability and complexity of higher type functions." In Proc. MSRI Workshop on Logic from Computer Science, Springer Verlag 1990.
• CK: S. Cook and B. Kapron, "Characterizations of the Basic Feasible Functionals of Finite Type", in Feasible Mathematics, S. R. Buss and P. J. Scott eds., Birkhauser, 1990
• Cl: P. Clote, "Sequential, machineindependent characterizations of the parallel complexity classes AlogTIME, ACk, NCk and NC." in MSI Workshop on Feasible Mathematics, Birkhauser, 1989.
• CU: S. Cook , A. Urquhart, Functional interpretations of feasibly constructive arithmetic, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.107-112, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73017]
• I: N. Immerman, "Descriptive and Computational Complexity", AMS Short Course in Complexity, 1988.
• L: Daniel Leivant, A foundational delineation of poly-time, Papers presented at the IEEE symposium on Logic in computer science, p.391-420, May 1994, Amsterdam, The Netherlands
• L2: D. Leivant, "Subrecursion and lambda representation over free algebras (Preliminary summary)", in Feasible Mathematics, S. Buss and P. Scott, eds., Birkhauser 1990.
• O: J. Otto, "Categorical Characterization of Ptime r', manuscript, Dept. Mathematics, McGill University, 1991.
• R: H. E. Rose, Subrecursion: functions and hierarchies, Oxford Logic Guides 9, Clarendon Press, Oxford, 1984.
• Ri: Ritchie, "Classes of Predictably Computable Functions", Transactions of the American Mathematical Society, v. 106, 1963.
• S: A. Seth, "There is no Recursive Axiomatization for Feasible Functionals of Type 2" in Proceedings of Logic in Computer Science, 1992 (to appear).
• T: G. J. Troulakis, Computability, Reston, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance, Theory