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)

  • 5
    $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Mar 18 '20 at 2:06
  • $\begingroup$ This paper claims that it overcomes the speedup theorem: arxiv.org/abs/cs/0206022 $\endgroup$ Mar 18 '20 at 17:46
  • $\begingroup$ @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) ... $\endgroup$ Mar 18 '20 at 23:04
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 18 '20 at 23:40
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 18 '20 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.