Algebras of feasible functions
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 210-214
- https://doi.org/10.1109/sfcs.1983.5
Abstract
What happens if we interpret the syntax of primitive recursive functions in finite domains rather than in the (Platonic) realm of all natural numbers? The answer is somewhat surprising: primitive recursiveness coincides with LOGSPACE computability. Analogously, recursiveness coincides with PTIME computability on finite domains (cf. [Sa]). Inductive definitions for some other complexity classes are discussed too.Keywords
This publication has 3 references indexed in Scilit:
- Relational queries computable in polynomial timeInformation and Control, 1986
- Languages which capture complexity classesPublished by Association for Computing Machinery (ACM) ,1983
- On relativization and the existence of complete setsPublished by Springer Nature ,1982