AC (complexity)

In <a href="/facts/Circuit_complexity/6EzA9Tty">circuit complexity</a>, AC is a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> hierarchy. Each class, ACi, consists of the <a href="/facts/Formal_language/crDTyP8q">languages</a> recognized by <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a> with depth 
 
 
 
 O
 (
 
 log
 
 i
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(\log ^{i}n)}
 
 and a <a href="/facts/Polynomial/Lzak8VVx">polynomial number</a> of <a href="/facts/Fanin/VfEexbKM">unlimited fan-in</a> <a href="/facts/AND_gate/tVKQD0w1">AND</a> and <a href="/facts/OR_gate/ox2lHgIM">OR gates</a>.
The name "AC" was chosen by analogy to <a href="/facts/NC_(complexity)/4SY2L2Kg">NC</a>, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to <a href="/facts/Alternating_Turing_machine/WktK7ADY">alternating Turing machines</a>.
The smallest AC class is <a href="/facts/AC0/UGJ79CeY">AC0</a>, consisting of constant-depth unlimited fan-in circuits.
The total hierarchy of AC classes is defined as

<blockquote>

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

</blockquote>

AC (complexity) open-in-new

AC (complexity)