<p>Classes of unary languages (above DLOGTIME) are just trivial variants of classes of usual, binary languages. Say, let us enumerate <span class="math-container">$\{0,1\}^*$</span> by natural numbers using the function <span class="math-container">$N(w_0\dots w_{n-1})=\sum_{i&lt;n}2^iw_i+2^n-1$</span>, and define the unary encoding of a language <span class="math-container">$L\in\{0,1\}^*$</span> to be <span class="math-container">$U(L)=\{1^{N(w)}:w\in L\}$</span>. Then straightforward padding arguments show:</p>
<ul>
<li><p>Unary languages in L are exactly the unary encodings of languages from <span class="math-container">$\mathrm{LinSPACE=DSPACE}(O(n))$</span>.</p>
</li>
<li><p>Unary languages in NL are exactly the unary encodings of languages from <span class="math-container">$\mathrm{NLinSPACE=NSPACE}(O(n))=\mathrm{CSL}$</span>.</p>
</li>
<li><p>Unary languages in P are exactly the unary encodings of languages from E.</p>
</li>
<li><p>Unary languages in NP are exactly the unary encodings of languages from NE.</p>
</li>
</ul>
<p>Therefore:</p>
<ul>
<li><p>There exist unary languages in <span class="math-container">$\mathrm{NL\setminus L}$</span> if and only if <span class="math-container">$\mathrm{LinSPACE\ne NLinSPACE}$</span>.</p>
</li>
<li><p>There exist unary languages in <span class="math-container">$\mathrm{P\setminus NL}$</span> if and only if <span class="math-container">$\mathrm{NLinSPACE\ne E}$</span>.</p>
</li>
<li><p>There exist unary languages in <span class="math-container">$\mathrm{NP\setminus P}$</span> if and only if <span class="math-container">$\mathrm{E\ne NE}$</span>.</p>
</li>
<li><p>The “hardest” (under DLOGTIME reductions) unary languages in NP are exactly the languages <span class="math-container">$U(L)$</span> where <span class="math-container">$L$</span> is NE-complete under linear-time reductions (such languages exist).</p>
</li>
</ul>
<p>Etc.</p>

CC BY-SA 4.0
2021-04-09T14:02:29.157Z
Should the $-1$ in the definition of $N$ be $+2^n$?
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-04-09T14:09:07.550Z
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
CC BY-SA 4.0
2021-04-09T06:15:51.580Z
2021-04-09T14:09:30.627Z
2021-04-09T14:09:30.627Z
Emil Jeřábek
<p>I am looking for some examples of unary languages lay between <span class="math-container">$L$</span> and <span class="math-container">$NP$</span>, i.e., <span class="math-container">$ L \subseteq NL \subseteq P = AL \subseteq NP $</span>.</p>
<p>What I found after some search(e.g., <a href="https://cstheory.stackexchange.com/questions/31448/complexity-zoo-for-unary-languages">Complexity zoo for unary languages</a>):</p>
<ul>
<li>It is not known whether there is a NP-Complete unary language.</li>
<li>There are many known results for automata models and sub-logarithmic space.</li>
<li>There seems no Zoo-style reference yet.</li>
</ul>
<p>For example, is there any unary language in <span class="math-container">$ NL $</span> but not known in <span class="math-container">$ L $</span>, in <span class="math-container">$ P $</span> but not known in <span class="math-container">$ NL $</span> or log-space alternating hierarchy?</p>
<p>Or, what are &quot;the hardest&quot; unary languages in <span class="math-container">$ NP $</span>?</p>

CC BY-SA 4.0
2021-04-09T05:23:30.543Z
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
CC BY-SA 4.0
2021-04-09T08:55:01.867Z
@EmilJeřábek 3-partition problem is unary NP-complete (No need to assume $P \ne NP$)
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-04-09T09:05:36.397Z
@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
CC BY-SA 4.0
2021-04-09T09:38:16.893Z
@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
CC BY-SA 4.0
2021-04-09T10:03:48.227Z
Thanks Emil for clarifying it.
Mohammad Al-Turkistany
<np-complete><unary-languages>
Unary language examples between L and NP
Abuzer Yakaryilmaz
# Unary language examples between L and NP

(Asked by: username_0 on 2021-04-09)

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](https://cstheory.stackexchange.com/questions/31448/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 $?

**Tags:** np-complete, unary-languages
> **Comments:**
> **username_1**: There are no NP-complete unary languages. The only reason this is “not known” is that this assumes $\mathrm{P\ne NP}$.  
> **username_2**: @EmilJeřábek 3-partition problem is unary NP-complete (No need to assume $P \ne NP$)  
> **username_3**: @Mohammad In case of 3-partition, the encoding of the input numbers can be given in unary, that does not make the language unary.  
> **username_1**: @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.  
> **username_2**: Thanks Emil for clarifying it.  

---

## 1 answers

### Answer by username_1 on 2021-04-09. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_4**: Should the $-1$ in the definition of $N$ be $+2^n$?  
> **username_1**: 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).  

---

