No Fastest Algorithm: Examples & Explanation

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Algorithm
Click For Summary

Discussion Overview

The discussion centers around the conjecture that there may not be a fastest algorithm for certain computational problems, particularly in the context of multiplication algorithms. Participants explore examples, implications, and the nature of algorithmic complexity, touching on both theoretical and practical aspects.

Discussion Character

  • Debate/contested
  • Exploratory
  • Technical explanation

Main Points Raised

  • Some participants propose that there is no fastest algorithm for multiplication, citing the work of Coppersmith and Winograd regarding matrix multiplication.
  • Others question whether simpler problems exist that could illustrate the absence of a fastest algorithm.
  • One participant mentions that matrix multiplication has not been definitively proven to lack a fastest algorithm, referencing a conjecture that suggests the existence of an O(n^2) algorithm under certain conditions.
  • There is a suggestion that for any computable task, infinitely many algorithms can be constructed, leading to the possibility of infinite ascending chains of complexity, raising the question of whether infinite descending chains might also exist.
  • Another participant argues that since there are only a finite number of ways to arrange code, a fastest algorithm must exist, unless infinite code lengths are considered.
  • One participant points out that different types of Toom-Cook multiplication provide examples of algorithms that do not satisfy the original question about having a fastest algorithm.

Areas of Agreement / Disagreement

Participants express differing views on the existence of a fastest algorithm, with some supporting the conjecture that none exists while others believe that a fastest algorithm must be possible due to the finite arrangements of code. The discussion remains unresolved with multiple competing perspectives.

Contextual Notes

Some claims rely on conjectures that have not been proven, and the discussion includes assumptions about computability and the nature of algorithmic complexity that are not universally accepted.

Dragonfall
Messages
1,023
Reaction score
5
It has been conjectured that there is no fastest algorithm for multiplication, among other things. Can somebody give me an example of something that provably has no fastest algorithm for?
 
Mathematics news on Phys.org
Here's a partial answer -- the best I could do at the moment. Coppersmith & Winograd show that there is no fastest "Strassen-type bilinear" matrix multiplication.

D. Coppersmith and S. Winograd, "On the Asymptotic Complexity of Matrix Multiplication", SIAM J. Comput. 11:3 (1982), pp. 472-492.
 
But is there a simple problem, even something completely artificial, that shows this CAN happen?
 
Matrix multiplication not simple enough for you? Maybe you need to say what you mean by 'simple'.
 
Matrix multiplication has not been proven either way, and in fact according to http://arxiv.org/abs/math.GR/0511460, if a certain conjecture is true, then there is a fatest algorithm that's in O(n^2).
 
Surely there has to be a 'fastest' algorithm, or at least an algorithm that's joint fastest. Perhaps that's what it means?
 
Here are some heuristics on why there might not be a fastest algorithm for something. For any given computable task, there are always infinitely many algorithms to solve it, because you can always add "futile" steps that just waste time, adding to the complexity. Therefore, there always exists an infinite ascending chain of slower and slower complexity classes which contain these algorithms. The question is, is it possible that infinite descending chains also exist?

EDIT: I want something computable, because any uncomputable problem trivially has no fastest solution.
 
Last edited:
Oh right I think I see. But since there only a finite number of ways of arranging code, then the fastest algorithm has to exist anyway. Unless you're talking about infinite length of code as well?
 
  • #10
Twinbee said:
Oh right I think I see. But since there only a finite number of ways of arranging code, then the fastest algorithm has to exist anyway. Unless you're talking about infinite length of code as well?

?

The number of finite programs is infinite.
 
  • #11
Dragonfall said:
The question is, is it possible that infinite descending chains also exist?

Of course. The different types of Toom-Cook multiplication are an easy example. Of course there are algorithms that outperform all of them, so they don't satisfy your original question.
 

Similar threads

Graduate Non-sinusoidal waveform model
  • · Replies 2 ·
Replies
2
Views
2K
High School Examples of Non-Algorithmic Math in Penrose's Book?
  • · Replies 12 ·
Replies
12
Views
4K
Undergrad Gradient descent algorithm and optimizers
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Is an algorithm for a proof required to halt?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Karatsuba multiplication implementation question
  • · Replies 3 ·
Replies
3
Views
2K
An Algorithm Challenge (finding the five fastest horses out of a large group)
  • · Replies 65 ·
3
Replies
65
Views
6K
Undergrad An algorithm for data compression?
  • · Replies 13 ·
Replies
13
Views
4K
Comp Sci I need a solved numerical example on genetic algorithm for 1 iteration
  • · Replies 11 ·
Replies
11
Views
2K
Algorithms for Traveling Purchaser Problem (TPP)
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Displacement-Rotation Algorithm
  • · Replies 2 ·
Replies
2
Views
2K