<p>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.</p>
<p>However, one can consider sublogarithmic circuit classes like uniform <span class="math-container">$AC_0$</span> and <span class="math-container">$NC_1$</span>. These have nice descriptive complexity descriptions: <span class="math-container">$AC_0=FO(+,\times)$</span> and for <span class="math-container">$NC_1$</span> see <a href="https://cstheory.stackexchange.com/questions/46644/what-is-foregular-the-descriptive-complexity-equivalent-of-nc1">here</a>. In terms of implicit complexity, I am aware of this <a href="https://arxiv.org/pdf/1201.1120.pdf" rel="nofollow noreferrer">work</a> that attempts a characterisation using proof nets.</p>
<p>On a different note, there is a nice characterisation of <span class="math-container">$L$</span> (and <span class="math-container">$NL$</span> respectively) by <span class="math-container">$k$</span>-pebble deterministic (non-deterministic respectively) automata. Maybe, there are some natural restrictions out there of these to capture sublogarithmic classes.</p>

CC BY-SA 4.0
2023-08-27T23:44:37.447Z
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.
Jake
CC BY-SA 4.0
2023-08-15T12:58:58.927Z
2023-08-15T12:58:58.927Z
Faustus
<p>Let <span class="math-container">$SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$</span> 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.</p>
<p>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 <span class="math-container">$L$</span> and <span class="math-container">$P$</span> have characterizations due to Jones and Bellantoni/Cook respectively as restricted programming languages.</p>
<p>Are there any good known implicit characterizations / descriptive complexity approaches to sublogarithmic space (specifically any subclasses of <span class="math-container">$SUBLOG$</span>)? 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.</p>

CC BY-SA 4.0
2023-09-15T16:03:59.633Z
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.
Siddharth
CC BY-SA 4.0
2023-09-15T16:06:50.257Z
That said, I wonder whether there's a characterization of SUBLOG in terms of Neil Jones' cons-free programs
Siddharth
CC BY-SA 4.0
2024-05-12T02:21:02.857Z
isn't that just empty set?
Kaveh
<space-bounded><descriptive-complexity>
Implicit characterization of sublogarithmic space
Jake
# Implicit characterization of sublogarithmic space

(Asked by: username_0 on 2023-07-18)

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.

**Tags:** space-bounded, descriptive-complexity
> **Comments:**
> **username_1**: 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.  
> **username_1**: That said, I wonder whether there's a characterization of SUBLOG in terms of Neil Jones' cons-free programs  
> **username_2**: isn't that just empty set?  

---

## 1 answers

### Answer by username_3 on 2023-08-15. Score: 1

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](https://cstheory.stackexchange.com/questions/46644/what-is-foregular-the-descriptive-complexity-equivalent-of-nc1). In terms of implicit complexity, I am aware of this [work](https://arxiv.org/pdf/1201.1120.pdf) 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.

> **Comments:**
> **username_0**: 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.  

---

