Metraipolis › archive › dc_b2a79bb0b09b
AC (complessità) — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/AC_(complessit%C3%A0)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T17:12:17.765Z
- SHA-256 of the archived text
42050a0267f65bac5554aea293da8f7bc5ffc7685b6405f6395426cffa75c4be- Stable URL of this page
https://metraipolis.com/documento/dc_b2a79bb0b09b
How to cite
AC (complessità) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/AC_(complessit%C3%A0) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_b2a79bb0b09b (Metraipolis archive dc_b2a79bb0b09b, sha256 42050a0267f65bac5554aea293da8f7bc5ffc7685b6405f6395426cffa75c4be)
BibTeX
@misc{dcb2a79bb0b09b,
title = {AC (complessità) — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/AC_(complessit%C3%A0)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_b2a79bb0b09b; sha256 42050a0267f65bac5554aea293da8f7bc5ffc7685b6405f6395426cffa75c4be},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/AC_(complessit%C3%A0). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, ACi, consiste dei linguaggi riconosciuti dai circuiti booleani con profondità O ( log i n ) {\displaystyle O(\log ^{i}n)} e un numero polinomiale di porte AND e OR, con un numero massimo di linee d'ingresso (fan-in) illimitato. Il nome "AC" fu scelto per analogia con NC, con la "A" nel nome che sta per "alternante" e si riferisce sia all'alternanza tra le porte AND e OR nei circuiti sia alle macchine di Turing alternanti. La classe AC è AC0, che consiste di circuiti con numero massimo di linee d'ingresso illimitato a profondità costante. La gerarchia totale delle classi AC è definita come 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 italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «AC (complessità)» — https://it.wikipedia.org/wiki/AC_(complessit%C3%A0)
Wikidata Q182336: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q182336
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/AC_(complessit%C3%A0)?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 139529858, consultata il 2026-10-07T16:43:10.587Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 63d06b9f219ea6e3871c41f4dc59cf89732e93d93b49f637c826438b15926c93