ACC (complexity)

ACC (complexity)

ACC is a hierarchy of complexity classes used in circuit complexity. Like the AC and NC classes, ACC is actually an infinite hierarchy of classes ACC^i.

The class ACC^i [m] is the class AC^i with the addition of gates which calculate the modulus modulo "m". We also have the class

mbox{ACC}^i = igcup_{m geq 2}mbox{AC}^i [m]
(Vollmer 1999, p. 126).

References

*cite book | last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | id = ISBN 3-540-64310-9


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • ACC — may refer to:Anatomy* Agenesis of the corpus callosum, a rare birth defect in which there is a complete or partial absence of the corpus callosum * Anterior cingulate cortex, the frontal part of the cingulate cortexBusiness* ACCBank, a commercial …   Wikipedia

  • AC (complexity) — In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth O(log^i n) and a polynomial number of unlimited fanin AND and OR gates.The smallest AC class is AC0,… …   Wikipedia

  • Circuit complexity — In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them. A Boolean circuit with n input bits …   Wikipedia

  • Canadian National Vimy Memorial — Veterans Affairs Canada Commonwealth War Graves Commission …   Wikipedia

  • Advanced Audio Coding — AAC redirects here. For other uses, see AAC (disambiguation). Advanced Audio Codings iTunes standard AAC file icon Filename extension .m4a, .m4b, .m4p, .m4v, .m4r, .3gp, .mp4, .aac Internet media type audio/aac, audio/aacp, au …   Wikipedia

  • Johann Sebastian Bach — redirect|BachJohann Sebastian Bach (pronounced|joˈhan/ˈjoːhan zeˈbastjan ˈbax) (31 March 1685 smaller| [O.S. 21 March] ndash; 28 July 1750) was a German composer and organist whose sacred and secular works for choir, orchestra, and solo… …   Wikipedia

  • Genetic code — A series of codons in part of a messenger RNA (mRNA) molecule. Each codon consists of three nucleotides, usually representing a single amino acid. The nucleotides are abbreviated with the letters A, U, G and C. This is mRNA, which uses U (uracil) …   Wikipedia

  • Late-2000s financial crisis — The TED spread (in red) increased significantly during the financial crisis, reflecting an increase in perceived credit risk …   Wikipedia

  • Social Protection — ▪ 2006 Introduction With medical costs skyrocketing and government programs scaled back, citizens bore more responsibility for their health care costs; irregular migration, human trafficking, and migrant smuggling posed challenges for… …   Universalium

  • Lisp (programming language) — Infobox programming language name = Lisp paradigm = multi paradigm: functional, procedural, reflective generation = 3GL year = 1958 designer = John McCarthy developer = Steve Russell, Timothy P. Hart, and Mike Levin latest release version =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”