# 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 "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}$. Apr 9, 2021 at 5:23
• @EmilJeřábek 3-partition problem is unary NP-complete (No need to assume $P \ne NP$) Apr 9, 2021 at 8: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. Apr 9, 2021 at 9: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. Apr 9, 2021 at 9:38
• Thanks Emil for clarifying it. Apr 9, 2021 at 10:03

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

• Should the $-1$ in the definition of $N$ be $+2^n$? Apr 9, 2021 at 14:02
• 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). Apr 9, 2021 at 14:09