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.