0
$\begingroup$

Let $k \in \mathbb{N} $ and define the language $L = \{ n,m | n^k = m \}$

Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in worse case for some polynomials $f,h$. now, by the Linear speedup theorem we can improve this to $\frac{f(|n|+|m|) + h(k)}{h(k)} = O(f(|n|+|m|))$ This means that for whatever $k$ we choose there is a (deterministic) TM deciding it in $O(f(|n|+|m|))$ even for cases $|n+m|<<k$. And this seemingly doesn't make sense, because it leads me to the fact that for every two choises of $k$ there are TM's deciding the corresponding languages in the same running time. What am I missing here?

$\endgroup$
  • $\begingroup$ $h(k)$ is a constant ... ($k$ is not part of the input string) ... $\endgroup$ – Vor Apr 11 at 12:43
  • $\begingroup$ I know but this means that if there is a TM deciding the corresponding language for k=2 in $f(|n|+|m|)$ time then there is one for k=100 in the same $f(|n|+|m|)$ time. also for $k=10^{100}$. but for k=2 it takes $O((|n|+|m|)^2)$. so it is possible to do it for $k= 10^{100}$ in $O((|n|+|m|)^2)$ as well? $\endgroup$ – Oren Apr 11 at 13:00
  • 1
    $\begingroup$ Yes, the speedup works because you can expand the alphabet (and the transition table of the TM). As a quick example you can think what happens if you write $n,m$ in binary $(n_2, m_2)$ and $n,m$ in hexadecimal $(n_{h}, m_{h})$: you get $|n_2| + |m_2| = 4 (|n_{h}| + m_{h}|)$ ... e.g. if $n=m=1024$ you switch from $10000000000_2,10000000000_2$ to $400_{h},400_{h}$. So with a larger alphabet you can "reduce" the input string and work faster. $\endgroup$ – Vor Apr 11 at 13:11
  • 1
    $\begingroup$ ... also note that the packing time is not considered because you can scan the input tape and "rewrite" it in packed form with the expanded alphabet on the working tape in a single pass. If the TM has only one tape, then you must also deal with the "packing time" $O(|x|^2)$ which cannot be avoided. $\endgroup$ – Vor Apr 11 at 13:21
0
$\begingroup$

The linear speedup theorem says that, for any constant $c$, you can decide the language $c$ times faster. It does not say that you can make it faster by some non-constant function.

The speedup theorem works by defining a new Turing machine that writes $c$ characters of the old Turing machine in a single tape cell, and then adjusting the transition function so that it simulates in a single step everything that the original machine did between entering and leaving each $c$-character block. If $c$ is a constant, it doesn't depend on the input, so you just compute the new machine once and use it on whatever input you want. But if you want $c$ to be some non-constant function, then you have to figure out what the new machine is every time you run it. That takes exponentially long, since there are exponentially many possible $c$-character blocks that you have to figure out the transition function for.

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