1
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 12:35
  • $\begingroup$ So you choose M' and M to be (one of) the fastest deciders for their language? $\endgroup$ – adrianN Aug 5 '16 at 13:22
  • $\begingroup$ No, the shortest. $\endgroup$ – user41014 Aug 5 '16 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 '16 at 13:28
  • 1
    $\begingroup$ It is still not true that smaller languages need more time, see my answer. $\endgroup$ – adrianN Aug 5 '16 at 13:32
0
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

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