| 词条 | AC0 |
| 释义 |
Example problemsInteger addition and subtraction are computable in AC0,[1] but multiplication is not (at least, not under the usual binary or base-10 representations of integers). Descriptive complexityFrom 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.[2] SeparationsIn 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC0 circuits, even with non-uniformity.[3][4] It follows that AC0 is not equal to NC1, because a family of circuits in the latter class can compute parity.[4] 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. References1. ^{{cite web|title=Lecture 2: The Complexity of Some Problems|url=http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf|first1=David Mix|last1=Barrington|first2=Alexis|last2=Maciel|work=IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity|date=July 18, 2000}} {{ComplexityClasses}}2. ^{{cite book | last = Immerman | first = N. | author-link = Neil Immerman | page = 85 | publisher = Springer | title = Descriptive Complexity | year = 1999}} 3. ^{{cite journal | zbl=0534.94008 | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984}} 4. ^1 2 3 {{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | author1-link=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=Cambridge University Press | year=2009 | isbn=978-0-521-42426-4 | pages=117–118, 287}} 2 : Circuit complexity|Complexity classes |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。