Algebras of Feasible Functions
- Yuri Gurevich
24th Annual Symposium on Foundations of Computer Science IEEE Computer Society Press |
We prove that, under a natural interpretation over finite domains,
(i) a function is primitive recursive if and only if it is logspace computable, and
(ii)a function is general recursive if and only if it is polynomial time computable.