TC (complexity)

<h2 id="relation-to-nc-and-ac">Relation to NC and AC</h2>
The relationship between the TC, <a href="/facts/NC_(complexity)/4SY2L2Kg">NC</a> and the <a href="/facts/AC_(complexity)/zL9RfPbm">AC</a> hierarchy can be summarized as follows:

NC
            
          
          
            i
          
        
        ⊆
        
          
            
              AC
            
          
          
            i
          
        
        ⊆
        
          
            
              TC
            
          
          
            i
          
        
        ⊆
        
          
            
              NC
            
          
          
            i
            +
            1
          
        
        .
      
    
    {\displaystyle {\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{TC}}^{i}\subseteq {\mbox{NC}}^{i+1}.}

In particular, we know that

NC
            
          
          
            0
          
        
        ⊊
        
          
            
              AC
            
          
          
            0
          
        
        ⊊
        
          
            
              TC
            
          
          
            0
          
        
        ⊆
        
          
            
              NC
            
          
          
            1
          
        
        .
      
    
    {\displaystyle {\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.}

The first strict containment follows from the fact that NC0 cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC0 and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC0 ⊊ TC0 follows because parity and majority (which are both in TC0) were shown to be not in AC0.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
As an immediate consequence of the above containments, we have that NC = AC = TC.

<ul><li>Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-64310-9.</li></ul>

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

<ol>
<li id="fn:1">Parberry, Ian; Schnitger, Georg (June 1988). "Parallel computation with threshold functions". Journal of Computer and System Sciences. 36 (3): 278–302. doi:10.1016/0022-0000(88)90030-X. <a href="https://linkinghub.elsevier.com/retrieve/pii/002200008890030X" target="_blank">https://linkinghub.elsevier.com/retrieve/pii/002200008890030X</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Furst, Merrick; Saxe, James B.; Sipser, Michael (1984), "Parity, circuits, and the polynomial-time hierarchy", Mathematical Systems Theory, 17 (1): 13–27, doi:10.1007/BF01744431, MR 0738749. <a href="/wiki/James_B._Saxe" target="_blank">/wiki/James_B._Saxe</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio (ed.), Randomness and Computation (PDF), Advances in Computing Research, vol. 5, JAI Press, pp. 6–20, ISBN 0-89232-896-7, archived from the original (PDF) on 2012-02-22 <a href="0-89232-896-7" target="_blank">0-89232-896-7</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

TC (complexity) open-in-new

TC (complexity)