Metraipolis › archive › dc_07fd88ffedb6

AC (complexity) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/AC_(complexity)
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-06T23:40:18.905Z
SHA-256 of the archived text
8f84a9973d498a46e9eaf2ef6e88a9c4e4f00a0b5a84b4a1e1577da62e5e5816
Stable URL of this page
https://metraipolis.com/documento/dc_07fd88ffedb6

How to cite

AC (complexity) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/AC_(complexity) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_07fd88ffedb6 (Metraipolis archive dc_07fd88ffedb6, sha256 8f84a9973d498a46e9eaf2ef6e88a9c4e4f00a0b5a84b4a1e1577da62e5e5816)
BibTeX
@misc{dc07fd88ffedb6,
  title = {AC (complexity) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/AC_(complexity)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_07fd88ffedb6; sha256 8f84a9973d498a46e9eaf2ef6e88a9c4e4f00a0b5a84b4a1e1577da62e5e5816},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/AC_(complexity). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 ) {\displaystyle O(\log ^{i}n)} and a polynomial number of unlimited fan-in AND and OR gates. The name "AC" was chosen by analogy to NC, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to alternating Turing machines. The smallest AC class is AC0, consisting of constant-depth unlimited fan-in circuits. The total hierarchy of AC classes is defined as AC = ⋃ i ≥ 0 AC i {\displaystyle {\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}}

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «AC (complexity)» — https://en.wikipedia.org/wiki/AC_(complexity)
Wikidata Q182336: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q182336
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/AC_(complexity)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1312462261, consultata il 2026-11-06T23:35:44.832Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ac07e5465b70fac1e39c053ccb93e88314e763a8eb745098aa66f3d73e14baab