Space Complexity Classes

In earlier work, we have studied the relationship between Light Affine Logic and the Bellantoni-Cook function algebra $BC$, which are both resource-free characterizations of polytime computable functions, and considered the question of interpreting one in the other. We aim to find versions of the two systems that characterize the standard space complexity classes such as L (Logspace), NL (Non-deterministic Logspace), NP and PSPACE. A priority is to examine the ``feasible'' space complexity classes: L and NL. In joint work with Mairson, we have shown that numeric functions definable in $BC^-$ (a linear version of $BC$ introduced in [MO01a]) are L-computable because of an invariance. (By the invariance, we can infer, for instance, that the definition-by-case construct and the even-shift functions in [MO01a] are not definable in $BC^-$.) A natrual question is to find out what needs to be added to $BC^-$ to make it L-complete or NL-complete. (It seems highly unlikely that $BC^-$ functions are NC(1)-computable.) A difficulty has to do with the fact that L-computable numeric functions may well return results that are polynomially long. As a first approximation, we will look at functions in L that have ``short'' ($\log{n}$-sized) ouput.