Tailoring Recursion for Complexity
Gradel, Erich ; Gurevich, Yuri
J. Symbolic Logic, Tome 60 (1995) no. 1, p. 952-969 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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 $\mathrm{AC}^1$-circuits.
Publié le : 1995-09-14
Classification:  
@article{1183744816,
     author = {Gradel, Erich and Gurevich, Yuri},
     title = {Tailoring Recursion for Complexity},
     journal = {J. Symbolic Logic},
     volume = {60},
     number = {1},
     year = {1995},
     pages = { 952-969},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744816}
}

Gradel, Erich; Gurevich, Yuri. Tailoring Recursion for Complexity. J. Symbolic Logic, Tome 60 (1995) no. 1, pp.  952-969. http://gdmltest.u-ga.fr/item/1183744816/