Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
AC0
open-in-new
<p>AC0 (alternating circuit) is a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> used in <a href="/facts/Circuit_complexity/6EzA9Tty">circuit complexity</a>. It is the smallest class in the <a href="/facts/AC_(complexity)/zL9RfPbm">AC</a> hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-<a href="/facts/Fanin/VfEexbKM">fanin</a> <a href="/facts/AND_gate/tVKQD0w1">AND gates</a> and <a href="/facts/OR_gate/ox2lHgIM">OR gates</a> (we allow <a href="/facts/NOT_gate/pGk3qGTI">NOT gates</a> only at the inputs). It thus contains <a href="/facts/NC_(complexity)/4SY2L2Kg">NC0</a>, which has only bounded-fanin AND and OR gates. Such circuits are called "alternating circuits", since it is only necessary for the layers to alternate between all-AND and all-OR, since one AND after another AND is equivalent to a single AND, and the same for OR. </p>