Unary language examples between L and NP

Question

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 "the hardest" unary languages in $ NP $?

There are no NP-complete unary languages. The only reason this is “not known” is that this assumes $\mathrm{P\ne NP}$. — Emil Jeřábek, Apr 09 '21 at 05:23
@EmilJeřábek 3-partition problem is unary NP-complete (No need to assume $P \ne NP$) — Mohammad Al-Turkistany, Apr 09 '21 at 08:55
@Mohammad In case of 3-partition, the encoding of the input numbers can be given in unary, that does not make the language unary. — domotorp, Apr 09 '21 at 09:05
@Mohammad What domotorp said. The whole input has to be represented in unary for a language to be unary. If P $\ne$ NP, then no unary language (and more generally, no sparse language) is NP-complete. — Emil Jeřábek, Apr 09 '21 at 09:38

Emil Jeřábek · Accepted Answer · 2021-04-09T14:09:30.627

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<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.

Thanks for spotting the typo. It should be ${}+2^n-1$ (the ${}-1$ is to make it a bijection: otherwise $N(w)\ge1$ for all $w$, hence the unary empty string is left out). — Emil Jeřábek, Apr 09 '21 at 14:09

Unary language examples between L and NP

1 Answers1