<p>Short &quot;naive&quot; question:</p>
<blockquote>
<p>Is it true that faster algorithms require longer programs ?</p>
</blockquote>
<p>Given a decision problem <span class="math-container">$A$</span> and a reasonable model of computation, there can be many ways (algorithms) to solve it, and some of them can be extremely inefficient or extremely efficient (when the time complexity of the algorithm matches the time complexity of the problem). For example the primality test can be done using the <em>Sieve of Eratosthenes</em> algorithm which is quite simple but requires exponential time or the <em>AKS primality test</em> which runs in polynomial time but is rather complex and requires a &quot;lot of code&quot;.</p>
<blockquote>
<p>Are there other examples of problems that can be solved &quot;slowly&quot; by a very simple algorithm, but the most efficient algorithm known is very complicated and requires a much bigger program?</p>
<p>What could be the underlying explanation for such behviour? (e.g. Kolmogorov complexity seems not to play any role)</p>
</blockquote>

CC BY-SA 4.0
2020-03-18T02:06:14.987Z
Not sure if this is what you're looking for, but Blum's speed-up theorem shows that there exists an (artificial) problem such that for any program you may write, there exists a longer program that solve the problem substantially more efficiently.
Yonatan N
CC BY-SA 4.0
2020-03-18T17:46:06.117Z
This paper claims that it overcomes the speedup theorem: https://arxiv.org/abs/cs/0206022
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-03-18T23:04:02.927Z
@YonatanN: thanks! But I'm more interested in examples of "natural" problems (and if the rule faster-bigger also applies to them, or there is a counterexample) ...
Marzio De Biasi
CC BY-SA 4.0
2020-03-18T23:10:35.127Z
@MohammadAl-Turkistany: very interesting ... I'll read it!
Marzio De Biasi
CC BY-SA 4.0
2020-03-18T23:40:18.017Z
Hutter search doesn't 'overcome' Blum, Hutter search doesn't terminate on programs where an asymptotic bound cannot be proven in the ambient logic that Hutter search diagonalises over.
Martin Berger
CC BY-SA 4.0
2020-03-18T23:42:13.313Z
Hutter search is optimal only asymptotically. In practise even a simple sorting problem will probably take longer than the universe exists -- after all Hutter search diagonalies threefold: over all programs $P$, all time bounds $t$ and proofs that $t$ is a time-bound for $P$.
Martin Berger
CC BY-SA 4.0
2020-03-18T23:57:19.157Z
I think the way to interpret Hutter's result is that asymptotic time  complexity measures really break down and become useless when you allow programs that diagonalise over everything.
Martin Berger
<soft-question><time-complexity>
Program size versus program running time
Marzio De Biasi
# Program size versus program running time

(Asked by: username_0 on 2020-03-17)

Short "naive" question:

> Is it true that faster algorithms require longer programs ?

Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) to solve it, and some of them can be extremely inefficient or extremely efficient (when the time complexity of the algorithm matches the time complexity of the problem). For example the primality test can be done using the *Sieve of Eratosthenes* algorithm which is quite simple but requires exponential time or the *AKS primality test* which runs in polynomial time but is rather complex and requires a "lot of code".

> Are there other examples of problems that can be solved "slowly" by a very simple algorithm, but the most efficient algorithm known is very complicated and requires a much bigger program?
>
> What could be the underlying explanation for such behviour? (e.g. Kolmogorov complexity seems not to play any role)

**Tags:** soft-question, time-complexity

> **Comments:**
> **username_1**: Not sure if this is what you're looking for, but Blum's speed-up theorem shows that there exists an (artificial) problem such that for any program you may write, there exists a longer program that solve the problem substantially more efficiently.  
> **username_2**: This paper claims that it overcomes the speedup theorem: https://arxiv.org/abs/cs/0206022  
> **username_0**: @YonatanN: thanks! But I'm more interested in examples of "natural" problems (and if the rule faster-bigger also applies to them, or there is a counterexample) ...  
> **username_0**: @MohammadAl-Turkistany: very interesting ... I'll read it!  
> **username_3**: Hutter search doesn't 'overcome' Blum, Hutter search doesn't terminate on programs where an asymptotic bound cannot be proven in the ambient logic that Hutter search diagonalises over.  
> **username_3**: Hutter search is optimal only asymptotically. In practise even a simple sorting problem will probably take longer than the universe exists -- after all Hutter search diagonalies threefold: over all programs $P$, all time bounds $t$ and proofs that $t$ is a time-bound for $P$.  
> **username_3**: I think the way to interpret Hutter's result is that asymptotic time  complexity measures really break down and become useless when you allow programs that diagonalise over everything.  

---

## 0 answers

