AC0

AC0

AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all circuits of depth O(1) and polynomial size, with unlimited-fanin AND gates and OR gates. (We allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates.

From a descriptive complexity viewpoint, DLOGTIME-uniform AC0 is equal to the descriptive class FO+BIT of all languages describable in first-order logic with the addition of the BIT operator, or alternatively by FO(+, times).

In 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC0 circuits, even with non-uniformity. This leads us to a proof that AC0 is not equal to NC1 .

References

Search another word or see AC0on Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;