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

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

1 Answer 1

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.

$\endgroup$
2
  • $\begingroup$ Should the $-1$ in the definition of $N$ be $+2^n$? $\endgroup$ 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$ 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.