2
$\begingroup$

Consider a language $L$ such that $L \subseteq \Sigma^*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \{a\}^*$.

Can anything be said about the time complexity of $L$? Is it the case that $L \in P$?

I can't come up with any example of a language with a single symbol that is not in $P$.

$\endgroup$

1 Answer 1

4
$\begingroup$

The language $\{a^n : \text{ the $n$th Turing machine halts on the empty string} \}$ is undecidable.

In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.

$\endgroup$
3
  • $\begingroup$ Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable? $\endgroup$
    – denidare
    Commented Nov 1, 2018 at 21:38
  • 1
    $\begingroup$ Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations. $\endgroup$
    – Pål GD
    Commented Nov 1, 2018 at 22:03
  • 1
    $\begingroup$ Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time. $\endgroup$ Commented Nov 1, 2018 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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