4
$\begingroup$

Let $SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine with a read-only input tape.

We have good implicit characterizations of constant space, i.e. regular languages, such as regular expressions or finite-state machines. Likewise, many circuit classes or larger space/time classes have good implicit characterizations: constant-depth circuit classes have logical representations using quantifier types that correspond to the gates, while $L$ and $P$ have characterizations due to Jones and Bellantoni/Cook respectively as restricted programming languages.

Are there any good known implicit characterizations / descriptive complexity approaches to sublogarithmic space (specifically any subclasses of $SUBLOG$)? I know the lack of robustness of sublogarithmic space makes such a characterization unlikely, so I'd be happy even with partial results in this direction.

$\endgroup$
3
  • $\begingroup$ I think this reflects upon the distinction between implicit and descriptive complexity. The approach in implicit complexity is to take each datum (e.g. a string) as a single point, whereas in descriptive complexity a string is regarded as a finite structure. In practice, this means descriptive complexity is better at capturing small classes, though I'm not sure about sublogarithmic space. $\endgroup$
    – Siddharth
    Commented Sep 15, 2023 at 16:03
  • $\begingroup$ That said, I wonder whether there's a characterization of SUBLOG in terms of Neil Jones' cons-free programs $\endgroup$
    – Siddharth
    Commented Sep 15, 2023 at 16:06
  • $\begingroup$ isn't that just empty set? $\endgroup$
    – Kaveh
    Commented May 12 at 2:21

1 Answer 1

0
$\begingroup$

In general, sublogarithmic classes are not robust i.e. the class of problems is not invariant under the machine model chosen. This is partly because, in general, closure properties do not hold for such classes. In particular, Immerman-Szelencsenyi theorem (closure under complementation) and Savitch's theorem (closure under non-determinism) doesn't necessarily hold for sublogarithmic classes.

However, one can consider sublogarithmic circuit classes like uniform $AC_0$ and $NC_1$. These have nice descriptive complexity descriptions: $AC_0=FO(+,\times)$ and for $NC_1$ see here. In terms of implicit complexity, I am aware of this work that attempts a characterisation using proof nets.

On a different note, there is a nice characterisation of $L$ (and $NL$ respectively) by $k$-pebble deterministic (non-deterministic respectively) automata. Maybe, there are some natural restrictions out there of these to capture sublogarithmic classes.

$\endgroup$
1
  • $\begingroup$ But sublogarithmic space classes are known to be closed under complement, see "Halting Space-Bounded Computations" by Sipser. And a lack of (known) closure under nondeterminism doesn't really seem important in this case -- after all, $P$ and $L$ are not known to be closed under nondeterminism, but there are many implicit characterizations of both classes. $\endgroup$
    – Jake
    Commented Aug 27, 2023 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.