5
$\begingroup$

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 $?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ There are no NP-complete unary languages. The only reason this is “not known” is that this assumes $\mathrm{P\ne NP}$. $\endgroup$
    – Emil Jeřábek
    Apr 9, 2021 at 5:23
  • $\begingroup$ @EmilJeřábek 3-partition problem is unary NP-complete (No need to assume $P \ne NP$) $\endgroup$
    – Mohammad Al-Turkistany
    Apr 9, 2021 at 8:55
  • 7
    $\begingroup$ @Mohammad In case of 3-partition, the encoding of the input numbers can be given in unary, that does not make the language unary. $\endgroup$
    – domotorp
    Apr 9, 2021 at 9:05
  • $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Apr 9, 2021 at 9:38
  • $\begingroup$ Thanks Emil for clarifying it. $\endgroup$
    – Mohammad Al-Turkistany
    Apr 9, 2021 at 10:03

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Should the $-1$ in the definition of $N$ be $+2^n$? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Apr 9, 2021 at 14:02
  • $\begingroup$ 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). $\endgroup$
    – Emil Jeřábek
    Apr 9, 2021 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.