Tailoring recursion for complexity
- 1 September 1995
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 60 (3) , 952-969
- https://doi.org/10.2307/2275767
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 AC1 -circuits.Keywords
This publication has 16 references indexed in Scilit:
- Capturing complexity classes by fragments of second-order logicTheoretical Computer Science, 1992
- Datalog extensions for database queries and updatesJournal of Computer and System Sciences, 1991
- An algebra and a logic for NC1Information and Computation, 1990
- The complexity of optimization problemsJournal of Computer and System Sciences, 1988
- Fixed-point extensions of first-order logicAnnals of Pure and Applied Logic, 1986
- Relational queries computable in polynomial timeInformation and Control, 1986
- A logic for constant-depth circuitsInformation and Control, 1984
- Toward logic tailored for computational complexityLecture Notes in Mathematics, 1984
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960