- #1

- 1,030

- 4

**provably**has no fastest algorithm for?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Dragonfall
- Start date

- #1

- 1,030

- 4

- #2

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

D. Coppersmith and S. Winograd, "On the Asymptotic Complexity of Matrix Multiplication", SIAM J. Comput. 11:3 (1982), pp. 472-492.

- #3

- 1,030

- 4

But is there a simple problem, even something completely artificial, that shows this CAN happen?

- #4

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

Matrix multiplication not simple enough for you? Maybe you need to say what you mean by 'simple'.

- #5

- 1,030

- 4

- #6

- 117

- 0

- #7

- 1,030

- 4

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.

EDIT: I want something

Last edited:

- #8

- 367

- 1

http://www.scottaaronson.com/democritus/lec5.html

Indeed, there may not be a fastest algorithm for certain problems.

- #9

- 117

- 0

- #10

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

?

The number of finite programs is infinite.

- #11

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

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.

Share: