AC ⁰

AC ⁰ is a complexity class in circuit complexity , a branch of complexity theory . It contains all functions that can be calculated by circuit families with depth O (1) and polynomial size with AND gates and OR gates with unlimited fan-in , and possibly non-gates at the inputs. It is the smallest class in the AC hierarchy and is higher than NC ⁰ , which only allows gates with limited fan-in.

In descriptive complexity theory , DLOGTIME - uniform AC ⁰ corresponds to the descriptive class FO + BIT of the languages ​​that can be described in first-level logic with the BIT operator , the class FO (+, ), and the logarithmic hierarchy . ${\displaystyle \times }$

In 1984 Furst, Saxe and Sipser showed that the parity function is not in AC ⁰ . It follows that the majority function is not in AC ⁰ either . It follows that AC ^{0 is} not equal to NC ¹ . Addition and subtraction of whole numbers are in AC ⁰ , but multiplication is not (at least with the usual representations for base 2 or 10).

literature

• Stasys Jukna: Boolean function complexity. Advances and frontiers . Springer, 2012, ISBN 978-3-642-24507-7 .

Web links

• AC0 . In: Complexity Zoo. (English)

Individual evidence

1. ^ Neil Immerman : Descriptive complexity . Springer, 1999, p. 85 .
2. ^ M. Furst, JB Saxe and M. Sipser: Parity, circuits, and the polynomial-time hierarchy . In: Mathematical Systems Theory . tape 17 , 1984, pp. 13-27 , doi : 10.1007 / BF01744431 .
3. ^ Johan Håstad : Almost Optimal Lower Bounds for Small Depth Circuits . In: Silvio Micali (Ed.): Randomness and Computation . JAI Press, 1989, ISBN 0-89232-896-7 , pp. 6–20 ( online ( memento of February 22, 2012 in the Internet Archive ) [PDF; accessed on September 24, 2012]). Almost Optimal Lower Bounds for Small Depth Circuits ( Memento of the original dated February 22, 2012 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.