GetWiki
AC0
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
AC0
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
(File:Diagram of an AC0 Circuit.svg|thumbnail|Diagram of an AC0 circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a constant.){{DISPLAYTITLE:AC0}}AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of 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.- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
Example problems
Integer addition and subtraction are computable in AC0,WEB, Lecture 2: The Complexity of Some Problems,weblink David Mix, Barrington, Alexis, Maciel, IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity, July 18, 2000, but multiplication is not (specifically, when the inputs are two integers under the usual binaryWEB, Kayal, Neeraj, Neeraj Kayal, Hegde, Sumant, 2015, Lecture 5: Feb 4, 2015,weblink live, 2021-10-16, E0 309: Topics in Complexity Theory,weblink 2021-10-16, or base-10 representations of integers).Since it is a circuit class, like P/poly, AC0 also contains every unary language.Descriptive complexity
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 predicate, or alternatively by FO(+, Ã), or by Turing machine in the logarithmic hierarchy.BOOKSeparations
In 1984 Furst, Saxe, and Sipser showed that calculating the parity of the input bits (unlike the aforementioned addition/subtraction problems above which had two inputs) cannot be decided by any AC0 circuits, even with non-uniformity.JOURNAL, 0534.94008, Furst, Merrick, Saxe, James B., James B. Saxe, Sipser, Michael, Michael Sipser, 10.1007/BF01744431, 1, Mathematical Systems Theory, 738749, 13â27, Parity, circuits, and the polynomial-time hierarchy, 17, 1984, BOOK, 1193.68112, Arora, Sanjeev, Sanjeev Arora, Barak, Boaz, Computational complexity. A modern approach,weblink limited, Cambridge University Press, 2009, 978-0-521-42426-4, 117â118, 287, It follows that AC0 is not equal to NC1, because a family of circuits in the latter class can compute parity. More precise bounds follow from switching lemma. Using them, it has been shown that there is an oracle separation between the polynomial hierarchy and PSPACE.References
{{reflist}}{{ComplexityClasses}}- content above as imported from Wikipedia
- "AC0" does not exist on GetWiki (yet)
- time: 7:19am EDT - Sat, May 18 2024
- "AC0" does not exist on GetWiki (yet)
- time: 7:19am EDT - Sat, May 18 2024
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 23 MAY 2022
The Illusion of Choice
Culture
Culture
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
© 2024 M.R.M. PARROTT | ALL RIGHTS RESERVED