Unary language examples between L and NP I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $ L \subseteq NL \subseteq P = AL \subseteq NP $.
What I found after some search(e.g., Complexity zoo for unary languages):

It is not known whether there is a NP-Complete unary language.
There are many known results for automata models and sub-logarithmic space.
There seems no Zoo-style reference yet.

For example, is there any unary language in $ NL $ but not known in $ L $, in $ P $ but not known in $ NL $ or log-space alternating hierarchy?
Or, what are &quot;the hardest&quot; unary languages in $ NP $?
Classes of unary languages (above DLOGTIME) are just trivial variants of classes of usual, binary languages. Say, let us enumerate $\{0,1\}^*$ by natural numbers using the function $N(w_0\dots w_{n-1})=\sum_{i&lt;n}2^iw_i+2^n-1$, and define the unary encoding of a language $L\in\{0,1\}^*$ to be $U(L)=\{1^{N(w)}:w\in L\}$. Then straightforward padding arguments show:

Unary languages in L are exactly the unary encodings of languages from $\mathrm{LinSPACE=DSPACE}(O(n))$.

Unary languages in NL are exactly the unary encodings of languages from $\mathrm{NLinSPACE=NSPACE}(O(n))=\mathrm{CSL}$.

Unary languages in P are exactly the unary encodings of languages from E.

Unary languages in NP are exactly the unary encodings of languages from NE.


Therefore:

There exist unary languages in $\mathrm{NL\setminus L}$ if and only if $\mathrm{LinSPACE\ne NLinSPACE}$.

There exist unary languages in $\mathrm{P\setminus NL}$ if and only if $\mathrm{NLinSPACE\ne E}$.

There exist unary languages in $\mathrm{NP\setminus P}$ if and only if $\mathrm{E\ne NE}$.

The “hardest” (under DLOGTIME reductions) unary languages in NP are exactly the languages $U(L)$ where $L$ is NE-complete under linear-time reductions (such languages exist).


Etc.