Let $L' \subseteq L \subseteq \Sigma^*$ be decidable languages with deterministic Turing machines $M'$ and $M$ which decide the languages. Typically we have $t_M(w) \le t_{M'}(w)$ for all $w \in \Sigma^*$, where $t_M(w)$ is the time of $M$ on input $w$.

Suppose furthermore that $M$ and $M'$ have minimum length when interpreted on some chosen universal Turing machine $U$. So if $M''$ decides $L'$ then $l(M'')\ge l(M')$ where $l(M)$ is the length of $M$ when interpreted on $U$.

Is this just a coincidence of the chosen Turing machines, or does this property hold for all deciders of $L$ and $L'$ with minimum length?

"Typically" here means the following situation:

For instance if $L'$ is a decision problem on graphs and $L$ is the language of graphs (meaning that words correspond to adjacency matrix of a directed graph), then first for a word $w\in \Sigma^*$ one must decide if this word corresponds to an adjacency matrix of a graph, then decide if that graph has the property one is looking for. If you know a counterexample to that, that would also answer the question.

  • $\begingroup$ Why do we have that "typically"? If you don't provide more information about the TMs the runtime can be chosen almost arbitrarily. $\endgroup$
    – adrianN
    Aug 5, 2016 at 12:35
  • $\begingroup$ So you choose M' and M to be (one of) the fastest deciders for their language? $\endgroup$
    – adrianN
    Aug 5, 2016 at 13:22
  • $\begingroup$ No, the shortest. $\endgroup$
    – user41014
    Aug 5, 2016 at 13:24
  • $\begingroup$ Then how do you know that M doesn't do extra work? Maybe the shortest machine for L is terribly slow compared to the shortest machine for L'. $\endgroup$
    – adrianN
    Aug 5, 2016 at 13:28
  • 1
    $\begingroup$ It is still not true that smaller languages need more time, see my answer. $\endgroup$
    – adrianN
    Aug 5, 2016 at 13:32

2 Answers 2


We can make the relationship between $t_M$ and $t_{M^\prime}$ quite arbitrary. For example, consider $L$ the language of strings that encode a prime number, and $L^\prime$ the language of strings that encode either a prime number, or a satisfiable formula. Then $t_M<t_{M^\prime}$ if P$\not=$NP. On the other hand, if we choose $L^\prime=\Sigma^{\star}$, then $t_{M^\prime}<t_{M}$.


A counterexample is choosing L' as the empty language. That can be decided faster than most other languages.


Your Answer

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