Visualizza wikitesto di AC0

{{titolo errato|AC<sup>0</sup>}}
'''AC<sup>0</sup>''' è una [[classe di complessità]] usata nella [[complessità dei circuiti]]. È la classe più piccola della gerarchia [[AC (complessità)|AC]], e consiste di tutte le famiglie di circuiti che hanno profondità O(1) e dimensione polinomiale, con [[Porta AND|porte AND]] e [[Porta OR|porte OR]] con numero massimo di linee d'ingresso illimitato (''fan-in'') (ammettiamo le [[Porta NOT|porte NOT]] soltanto alle entrate).<ref name=AB118>Arora & Barak (2009) p. 118</ref> Essa perciò contiene '''NC<sup>0</sup>''', che ha soltanto porte AND e OR con numero massimo di linee d'ingresso limitato.<ref name=AB117>Arora & Barak (2009) p. 117</ref>

Da un punto di vista della complessità descrittiva, AC<sup>0</sup> [[Uniformità (complessità)|uniforme]] in [[DLOGTIME]] è uguale alla classe descrittiva [[FO (complessità)|FO]]+BIT di tutti i linguaggi descrivibili in una [[logica del primo ordine]] con l'aggiunta dell'[[operatore BIT]], o alternativamente da FO(+, <math>\times</math>), o da una macchina di Turing nella [[LH (complessità)|gerarchia logaritmica]].<ref>{{cita libro|Neil|Immerman|Descriptive complexity|1999|Springer-Verlag|città=New York|isbn=9780387986005|p=85}}</ref> 

Nel 1984 Furst, Saxe e Sipser dimostrarono che calcolare la [[Funzione di parità|parità]] di un'entrata non può essere decisa da nessun circuito AC<sup>0</sup>, anche con la non uniformità.<ref>{{cita testo | zbl=0534.94008 | cognome1=Furst | nome1=Merrick | cognome2=Saxe | nome2=James B. | cognome3=Sipser | nome3=Michael | titolo=Parity, circuits, and the polynomial-time hierarchy | rivista=Math. Syst. Theory | volume=17 | pp=13-27 | anno=1984 | issn=0025-5661 }}</ref><ref name=AB287>Arora & Barak (2009) p. 287</ref> Ne consegue che AC<sup>0</sup> non è uguale a [[NC1 (complessità)|NC<sup>1</sup>]], perché una famiglia di circuiti nell'ultima classe può computare la parità.<ref name=AB118/> Limiti più precisi conseguono dal [[lemma della commutazione]]. Usandoli, è stato dimostrato che c'è una separazione mediante oracolo tra [[Gerarchia polinomiale|PH]] e [[PSPACE]].

L'addizione e la sottrazione degli interi sono computabili in AC<sup>0</sup>, ma la moltiplicazione no (almeno, non in base alle abituali rappresentazioni binarie o in base 10 degli interi).

==Note==
<references/>

==Collegamenti esterni==
* {{cita libro | zbl=1193.68112 | cognome1=Arora | nome1=Sanjeev | wkautore1=Sanjeev Arora | cognome2=Barak | nome2=Boaz | titolo=Computational complexity. A modern approach | editore=Cambridge University Press | anno=2009 | isbn=978-0-521-42426-4 }}

{{Classi di complessità}}

{{Portale|Informatica|Matematica}}

[[Categoria:Classi di complessità]]