Gap theorem

<h2 id="gap-theorem">Gap theorem</h2>
<p>The general form of the theorem is as follows.
</p>
Suppose Φ is an <a href="/facts/Blum_axioms/INdJ9ygh">abstract (Blum) complexity measure</a>. For any <a href="/facts/Total_computable_function/dzwBlLGn">total computable function</a>  g for which 
  
    
      
        g
        (
        x
        )
        ≥
        x
      
    
    {\displaystyle g(x)\geq x}
  
 for every x, there is a total computable function t such that with respect to Φ, the <a href="/facts/Complexity_class/IIKrcTbP">complexity classes</a> with boundary functions t and 
  
    
      
        g
        ∘
        t
      
    
    {\displaystyle g\circ t}
  
 are identical.
<p>The theorem can be proved by using the Blum axioms without any reference to a concrete <a href="/facts/Computational_model/dq1CR6us">computational model</a>, so it applies to time, space, or any other reasonable complexity measure.
</p><p>For the special case of time complexity, this can be stated more simply as:
</p>
for any total computable function 
  
    
      
        g
        :
        
        ω
        
        →
        
        ω
      
    
    {\displaystyle g:\,\omega \,\to \,\omega }
  
 such that 
  
    
      
        g
        (
        x
        )
        ≥
        x
      
    
    {\displaystyle g(x)\geq x}
  
 for all x, there exists a time bound 
  
    
      
        T
        (
        n
        )
      
    
    {\displaystyle T(n)}
  
 such that 
  
    
      
        
          
            D
            T
            I
            M
            E
          
        
        (
        g
        (
        T
        (
        n
        )
        )
        )
        =
        
          
            D
            T
            I
            M
            E
          
        
        (
        T
        (
        n
        )
        )
      
    
    {\displaystyle {\mathsf {DTIME}}(g(T(n)))={\mathsf {DTIME}}(T(n))}
  
.
<p>Because the bound ⁠
  
    
      
        T
        (
        n
        )
      
    
    {\displaystyle T(n)}
  
⁠ may be very large (and often will be <a href="/facts/Constructible_function/MteaLvnF">nonconstructible</a>) the Gap Theorem does not imply anything interesting for complexity classes such as P or NP,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> and it does not contradict the <a href="/facts/Time_hierarchy_theorem/sm75DR1s">time hierarchy theorem</a> or <a href="/facts/Space_hierarchy_theorem/hUuCSeIj">space hierarchy theorem</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Blum%2527s_speedup_theorem/jQMKIla6">Blum's speedup theorem</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Fortnow, Lance; Homer, Steve (June 2003). "A Short History of Computational Complexity" (PDF). Bulletin of the European Association for Theoretical Computer Science (80): 95–133. Archived from the original (PDF) on 2005-12-29. <a href="https://web.archive.org/web/20051229063702/http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf" target="_blank">https://web.archive.org/web/20051229063702/http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column80.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Trakhtenbrot, Boris A. (1967). The Complexity of Algorithms and Computations (Lecture Notes). Novosibirsk University. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Borodin, Allan (1969). "Complexity classes of recursive functions and the existence of complexity gaps". In Fischer, Patrick C.; Ginsburg, Seymour; Harrison, Michael A. (eds.). Proceedings of the 1st Annual ACM Symposium on Theory of Computing, May 5–7, 1969, Marina del Rey, CA, USA. Association for Computing Machinery. pp. 67–78. <a href="/wiki/Allan_Borodin" target="_blank">/wiki/Allan_Borodin</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Borodin, Allan (January 1972). "Computational complexity and the existence of complexity gaps". Journal of the ACM. 19 (1): 158–174. doi:10.1145/321679.321691. hdl:1813/5899. <a href="https://doi.org/10.1145%2F321679.321691" target="_blank">https://doi.org/10.1145%2F321679.321691</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Allender, Eric W.; Loui, Michael C.; Regan, Kenneth W. (2014). "Chapter 7: Complexity Theory". In Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (eds.). Computing Handbook, Third Edition: Computer Science and Software Engineering. CRC Press. p. 7-9. ISBN 9781439898529. Fortunately, the gap phenomenon cannot happen for time bounds t that anyone would ever be interested in. <a href="9781439898529" target="_blank">9781439898529</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Zimand, Marius (2004). Computational Complexity: A Quantitative Perspective. North-Holland Mathematics Studies. Vol. 196. Elsevier. p. 42. ISBN 9780080476667.. <a href="9780080476667" target="_blank">9780080476667</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Gap theorem open-in-new

Gap theorem