2
$\begingroup$

I am trying to find a unary language whose runtime complexity is exponential in $n$ (e.g. $\Theta(2^n)$ or a similar expression). But I am not sure how to reason about the runtime of such languages.

I tried the language: $L_1=\{1^{2^k}\}$. This language can be identified by counting the number of ones in the input into a binary register, then checking if the binary register has only zeros and a leading one. This requires $O(n)$ steps to read the input, and probably $O(\log n)$ for each addition, so the total runtime is $O(n \log n)$. Is this correct?

What about the language: $L_2=\{1^{2^{2^k}}\}$? This language can be identified by counting the number of ones in the input into a binary register, then checking if the number of zeros in the register is in $L_1$. This seems like it can be done in time polynomial in $n$.

How can I construct a unary language that can only be identified in exponential time?

$\endgroup$
  • $\begingroup$ The empty language has runtime complexity $O(2^n)$. On the other hand, the language of $1^n$ such that $n$ is an encoding of a halting Turing machine has runtime complexity $\Omega(2^n)$. Perhaps you were after runtime complexity $\Theta(2^n)$? $\endgroup$ – Yuval Filmus Oct 20 '14 at 4:12
  • $\begingroup$ You are right, I corrected the question. $\endgroup$ – Erel Segal-Halevi Oct 20 '14 at 6:58
2
$\begingroup$

Let $L$ be a language in $\mathrm{TIME}(2^{2^n})$ but not in $\mathrm{TIME}(o(2^{2^n}/2^n))$ (such a language exists by the time hierarchy theorem). Define $U = \{1^n : n \in L\}$. Using an algorithm for $L$, we get that $U \in \mathrm{TIME}(2^n + O(n^2))$. Running the same argument backwards, we see that $U \notin \mathrm{TIME}(o(2^n/n))$ (here we use that $O(4^n) \ll 2^{2^n}/2^n$).

$\endgroup$
  • $\begingroup$ Okay, I am convinced that such a language exists, but can you give an example of such a language? $\endgroup$ – Erel Segal-Halevi Oct 20 '14 at 6:59
  • $\begingroup$ The time hierarchy theorem is constructive though not explicit. Try to look up languages conjectured to have doubly exponential time complexity. There must be some since some algorithms run in doubly exponential time. $\endgroup$ – Yuval Filmus Oct 20 '14 at 11:22

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.