TC (complexity)

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, and specifically <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> and <a href="/facts/Circuit_complexity/6EzA9Tty">circuit complexity</a>, TC (Threshold Circuit) is a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> of <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> that can be recognized by threshold circuits, which are <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a> with <a href="/facts/AND_gate/tVKQD0w1">AND</a>, <a href="/facts/OR_gate/ox2lHgIM">OR</a>, and <a href="/facts/Majority_gate/Ntpb4wDr">Majority gates</a>, or equivalently, <a href="/facts/Threshold_Logic_Unit/TSH6nsgg">threshold gates</a>. For each fixed i, the complexity class TCi consists of all languages that can be recognized by a family of threshold circuits of depth 
 
 
 
 O
 (
 
 log
 
 i
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(\log ^{i}n)}
 
, <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> size, and unbounded <a href="/facts/Fan-in/VfEexbKM">fan-in</a>. The class TC is defined via

TC
          
        
        =
        
          ⋃
          
            i
            ≥
            0
          
        
        
          
            
              TC
            
          
          
            i
          
        
        .
      
    
    {\displaystyle {\mbox{TC}}=\bigcup _{i\geq 0}{\mbox{TC}}^{i}.}

The class was proposed in 1988 to formalize the computational complexity of <a href="/facts/Neural_network_(machine_learning)/6V1jMlkx">artificial neural networks</a>.

TC (complexity) open-in-new

TC (complexity)