<p>This is essentially true for matrix multiplication, as shown in this paper: <a href="https://ieeexplore.ieee.org/document/4568320" rel="noreferrer">https://ieeexplore.ieee.org/document/4568320</a>.</p>
<p>The &quot;essentially&quot; is because what they actually show is that this is true for all <em>tensor-decomposition-based</em> algorithms for MM. The MM exponent <span class="math-container">$\omega$</span> is defined in terms of tensor rank and as far as I know all known generic MM algorithms (Strassen, Coppersmith-Winograd, improvements to CW from the last 10 years) use this framework. So, I think it's typically taken for granted that MM algorithms will use the framework. Nevertheless, I don't know of an argument that <em>any</em> algorithm for MM <em>must</em> use tensor decomposition, although maybe there is a simple one. Hopefully someone more familiar with this can weigh in.</p>

CC BY-SA 4.0
2024-09-06T19:31:12.633Z
Thanks Huck - I didn't know this was proved, and that's a very nice example of a natural function that (conditionally) does the job.
GMB
CC BY-SA 4.0
2024-09-07T00:00:58.103Z
It is not known that all such MM algorithms must be bilinear - Turing machines can do all sorts of things that aren't algebraically meaningful. But this is still a great theorem, at the very least in the flavor of the question!
Joshua Grochow
CC BY-SA 4.0
2024-09-06T17:52:49.427Z
2024-09-06T17:52:49.427Z
Huck Bennett
<p>Is there a problem where for all correct algorithms <span class="math-container">$A$</span>, letting <span class="math-container">$T(n)$</span> be the runtime of <span class="math-container">$A$</span>, there exists <span class="math-container">$\varepsilon &gt; 0$</span> and a correct algorithm <span class="math-container">$A'$</span> running in time <span class="math-container">$T(n)\cdot n^{-\varepsilon}$</span>?
This could happen, for example, if for all <span class="math-container">$k$</span> there is an algorithm running in time <span class="math-container">$O(n^{1+1/k})$</span>, but the function <span class="math-container">$f(k)$</span> that outputs the source code of the <span class="math-container">$k^{th}$</span> algorithm in the sequence is uncomputable.</p>
<p>I'm fine with a very artificial problem that provably has this property, I don't need it to be &quot;natural.&quot;  I'm most interested if we can name an explicit problem, with an unconditional proof that it has this property.  But failing that, existential results or proofs using standard assumptions from complexity theory are interesting as well.</p>

CC BY-SA 4.0
2024-09-06T19:03:46.923Z
https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem
Emil Jeřábek
CC BY-SA 4.0
2024-09-06T19:30:24.590Z
Thanks Emil!  I didn't know that theorem, and it seems to answer the question perfectly.
GMB
CC BY-SA 4.0
2024-09-08T02:19:27.803Z
@GMB This [older question of mine](https://cs.stackexchange.com/questions/155658/optimal-lookup-complexity-when-requiring-insertion-complexity-to-be-at-most-ma) is similar to what you're asking, with the caveat that "running time" is replaced with the number of comparisons needed to solve a problem, so there is no Turing Machine in sight. It is more of an information theory problem. But maybe you will find my answer interesting, since there is a naturally occurring example of speedup. :-)
Franklin Pezzuti Dyer
CC BY-SA 4.0
2024-09-08T15:30:04.760Z
Cool - thanks for the reference!
GMB
CC BY-SA 4.0
2024-09-28T06:24:14.953Z
The answer is yes even for the $O(n^{1+1/k})$ complexities your mention. The proof is somewhat analogous to Blum's speedup theorem proof; see my question and answer [Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?](https://cstheory.stackexchange.com/questions/39101/does-%e2%88%a9-%ce%b50-mathrmdtimeon2%ce%b5-mathrmdtimen2o1)
Dmytro Taranovsky
<cc.complexity-theory><time-complexity>
Is there a problem known to have no fastest algorithm, up to polynomials?
GMB
# Is there a problem known to have no fastest algorithm, up to polynomials?

(Asked by: username_0 on 2024-09-06)

Is there a problem where for all correct algorithms $A$, letting $T(n)$ be the runtime of $A$, there exists $\varepsilon > 0$ and a correct algorithm $A'$ running in time $T(n)\cdot n^{-\varepsilon}$?
This could happen, for example, if for all $k$ there is an algorithm running in time $O(n^{1+1/k})$, but the function $f(k)$ that outputs the source code of the $k^{th}$ algorithm in the sequence is uncomputable.

I'm fine with a very artificial problem that provably has this property, I don't need it to be "natural." I'm most interested if we can name an explicit problem, with an unconditional proof that it has this property. But failing that, existential results or proofs using standard assumptions from complexity theory are interesting as well.

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem  
> **username_0**: Thanks Emil!  I didn't know that theorem, and it seems to answer the question perfectly.  
> **username_2**: @username_0 This [older question of mine](https://cs.stackexchange.com/questions/155658/optimal-lookup-complexity-when-requiring-insertion-complexity-to-be-at-most-ma) is similar to what you're asking, with the caveat that "running time" is replaced with the number of comparisons needed to solve a problem, so there is no Turing Machine in sight. It is more of an information theory problem. But maybe you will find my answer interesting, since there is a naturally occurring example of speedup. :-)  
> **username_0**: Cool - thanks for the reference!  
> **username_3**: The answer is yes even for the $O(n^{1+1/k})$ complexities your mention. The proof is somewhat analogous to Blum's speedup theorem proof; see my question and answer [Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?](https://cstheory.stackexchange.com/questions/39101/does-%e2%88%a9-%ce%b50-mathrmdtimeon2%ce%b5-mathrmdtimen2o1)  

---

## 1 answers

### Answer by username_4 on 2024-09-06. Score: 7

This is essentially true for matrix multiplication, as shown in this paper: <https://ieeexplore.ieee.org/document/4568320>.

The "essentially" is because what they actually show is that this is true for all *tensor-decomposition-based* algorithms for MM. The MM exponent $\omega$ is defined in terms of tensor rank and as far as I know all known generic MM algorithms (Strassen, Coppersmith-Winograd, improvements to CW from the last 10 years) use this framework. So, I think it's typically taken for granted that MM algorithms will use the framework. Nevertheless, I don't know of an argument that *any* algorithm for MM *must* use tensor decomposition, although maybe there is a simple one. Hopefully someone more familiar with this can weigh in.

> **Comments:**
> **username_0**: Thanks Huck - I didn't know this was proved, and that's a very nice example of a natural function that (conditionally) does the job.  
> **username_5**: It is not known that all such MM algorithms must be bilinear - Turing machines can do all sorts of things that aren't algebraically meaningful. But this is still a great theorem, at the very least in the flavor of the question!  

---

