Blum's speedup theorem

<h2 id="speedup-theorem">Speedup theorem</h2>
<p>Given a <a href="/facts/Blum_complexity_measure/INdJ9ygh">Blum complexity measure</a> 
  
    
      
        (
        φ
        ,
        Φ
        )
      
    
    {\displaystyle (\varphi ,\Phi )}
  
 and a <a href="/facts/Total_function/0vJMw0Nm">total</a> computable function 
  
    
      
        f
      
    
    {\displaystyle f}
  
 with two parameters, then there exists a total <a href="/facts/Computable_predicate/dzwBlLGn">computable predicate</a> 
  
    
      
        g
      
    
    {\displaystyle g}
  
 (a <a href="/facts/Boolean_valued_function/uT7E8pqC">boolean valued</a> computable function) so that for every program 
  
    
      
        i
      
    
    {\displaystyle i}
  
 for 
  
    
      
        g
      
    
    {\displaystyle g}
  
, there exists a program 
  
    
      
        j
      
    
    {\displaystyle j}
  
 for 
  
    
      
        g
      
    
    {\displaystyle g}
  
 so that for <a href="/facts/Almost_all/KvHxUCCc">almost all</a> 
  
    
      
        x
      
    
    {\displaystyle x}

</p>

f
        (
        x
        ,
        
          Φ
          
            j
          
        
        (
        x
        )
        )
        ≤
        
          Φ
          
            i
          
        
        (
        x
        )
      
    
    {\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x)}

<p>
  
    
      
        f
      
    
    {\displaystyle f}
  
 is called the speedup function. The fact that it may be as fast-growing as desired
(as long as it is computable) means that the phenomenon of always having a program of smaller complexity remains even if by "smaller" we mean "significantly smaller" (for instance, quadratically smaller, exponentially smaller).
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/G%C3%B6del%27s_speed-up_theorem/UEr4jfuD">Gödel's speed-up theorem</a></li></ul>

<ul><li><a href="/facts/Manuel_Blum/fl3GKhvh">Blum, Manuel</a> (1967). <a href="http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf">"A Machine-Independent Theory of the Complexity of Recursive Functions"</a> (PDF). <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i>. 14 (2): 322–336. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321386.321395">10.1145/321386.321395</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15710280">15710280</a>.</li>
<li><a href="/facts/Peter_van_Emde_Boas/Mzl3CEla">Van Emde Boas, Peter</a> (1975). "Ten years of speedup". In Bečvář, Jiří (ed.). <i>Mathematical Foundations of Computer Science 1975 4th Symposium, Mariánské Lázně, September 1–5, 1975</i>. Lecture Notes in Computer Science. Vol. 32. Springer-Verlag. pp. 13–29. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-07389-2_179">10.1007/3-540-07389-2_179</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-07389-5..</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/BlumsSpeed-UpTheorem.html">"Blum's Speed-Up Theorem"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li></ul>

Blum's speedup theorem open-in-new

Blum's speedup theorem