1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

No fastest algorithm

  1. May 18, 2009 #1
    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?
     
  2. jcsd
  3. May 18, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. May 19, 2009 #3
    But is there a simple problem, even something completely artificial, that shows this CAN happen?
     
  5. May 19, 2009 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Matrix multiplication not simple enough for you? Maybe you need to say what you mean by 'simple'.
     
  6. May 19, 2009 #5
    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).
     
  7. May 24, 2009 #6
    Surely there has to be a 'fastest' algorithm, or at least an algorithm that's joint fastest. Perhaps that's what it means?
     
  8. May 24, 2009 #7
    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: May 24, 2009
  9. May 24, 2009 #8
  10. May 24, 2009 #9
    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?
     
  11. May 24, 2009 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    ?

    The number of finite programs is infinite.
     
  12. May 24, 2009 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: No fastest algorithm
  1. Algorithm explanation (Replies: 1)

  2. Search algorithm (Replies: 14)

  3. Math algorithm (Replies: 5)

  4. Nesting Algorithm (Replies: 1)

Loading...