Tailoring recursion for complexity

&
Journal of Symbolic Logic 60 (3):952-969 (1995)
  Copy   BIBTEX

Abstract

We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC 1 -circuits

Categories

Keywords

Reprint years

DOI

10.2307/2275767

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,394

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
Bounded iteration and unary functions.Stefano Mazzanti - 2005 - Mathematical Logic Quarterly 51 (1):89-94.
An application of category-theoretic semantics to the characterisation of complexity classes using higher-order function algebras.Martin Hofmann - 1997 - Bulletin of Symbolic Logic 3 (4):469-486.
Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas.Jarmo Kontinen - 2013 - Studia Logica 101 (2):267-291.
Higher type recursion, ramification and polynomial time.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.
Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
The $\mu$ -measure as a tool for classifying computational complexity.Karl-Heinz Niggl - 2000 - Archive for Mathematical Logic 39 (7):515-539.
On the complexity of finding paths in a two-dimensional domain I: Shortest paths.Arthur W. Chou & Ker-I. Ko - 2004 - Mathematical Logic Quarterly 50 (6):551-572.

Analytics

Added to PP
2009-01-28

Downloads
53 (#409,721)

6 months
19 (#153,996)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
Fixed-point extensions of first-order logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32:265-280.
The Intrinsic Computational Difficulty of Functions.Alan Cobham - 1965 - In Yehoshua Bar-Hillel (ed.), Logic, methodology and philosophy of science. Amsterdam,: North-Holland Pub. Co.. pp. 24-30.

Add more references