Abstract We investigate the computing power of function algebras defined by means of unbounded recursion on notation. We introduce a new function algebra between the logspace computable functions and the polynomial time computable functions. Such algebra allows us to introduce a new sufficient condition for the equality L=P.
A note on unbounded recursion and regressive functions
Mazzanti Stefano
2026-01-01
Abstract
Abstract We investigate the computing power of function algebras defined by means of unbounded recursion on notation. We introduce a new function algebra between the logspace computable functions and the polynomial time computable functions. Such algebra allows us to introduce a new sufficient condition for the equality L=P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
