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$ – orgesleka 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
1
$\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}$.

$\endgroup$
6
$\begingroup$

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

$\endgroup$

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.