0
$\begingroup$

Blum's Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other words, does there exist a language $L$ which is decided by some algorithm within $f(n)$ steps so that any other algorithm which solves the same problem also runs in $\Omega(f(n))$ steps? If $f$ is linear, this is trivially the case. But what about beyond linear? Just a nonconstructive existence proof would already be cool.

$\endgroup$
1
$\begingroup$

(Deterministic) TMs with a single tape can recognize palindromes in time $O(n^2)$. It has been proven that this time bound is optimal (see, e.g., this paper).

Also, the time hierarchy theorems give you an endless supply of such examples (though they are not natural problems, of course).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The first paper you cite seems to only prove its results under severe restrictions. I was hoping for something more general, ideally even encompassing nondeterministic machines. As for the time hierarchy theorems, they only give problems not in $O(f(n))$ for arbitrary $f$. But that doesn't mean that those problems actually have a fastest algorithm. $\endgroup$ – Sebastian Oberhoff Aug 7 '19 at 14:22
  • $\begingroup$ @SebastianOberhoff Whoops. Ended up linking wrong paper. This one also covers NTMs. $\endgroup$ – dkaeae Aug 7 '19 at 14:26
  • $\begingroup$ @SebastianOberhoff Also, I do not quite understand what you mean by the time hierarchy theorems not being relevant. They give an explicit construction of a language which can be decided in time $f(n)$ but not in time $g(n)$ for any $g \in o(f)$ (at least for NTMs; the DTM version does not qualify because of the $\log n$ slack factor). $\endgroup$ – dkaeae Aug 7 '19 at 14:30
  • $\begingroup$ That's a slight misstatement of the nondeterministic time hierarchy. a) there's a little +1 flying around in the exact statement of the theorem. b) We get a different language for every pair of functions $f, g$ rather than a single language that works for all $g$ "smaller than" $f$. $\endgroup$ – Sebastian Oberhoff Aug 7 '19 at 14:51
  • $\begingroup$ @SebastianOberhoff No, we do not quantify over pairs of $f$ and $g$. We have a fixed $f$ and the language is recognizable in time $f$. Then, for any $g$ with $g(n+1) \in o(f(n))$, the same language is not recognizable in time $g$; it works for every such $g$. The "+1" is trivia for most reasonable functions (e.g., polynomials and exponential functions). $\endgroup$ – dkaeae Aug 7 '19 at 16:17

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.