AC0

Template:Titolo errato AC⁰ è una classe di complessità usata nella complessità dei circuiti. È la classe più piccola della gerarchia AC, e consiste di tutte le famiglie di circuiti che hanno profondità O(1) e dimensione polinomiale, con porte AND e porte OR con numero massimo di linee d'ingresso illimitato (fan-in) (ammettiamo le porte NOT soltanto alle entrate). Essa perciò contiene NC⁰, che ha soltanto porte AND e OR con numero massimo di linee d'ingresso limitato.

Da un punto di vista della complessità descrittiva, AC⁰ uniforme in DLOGTIME è uguale alla classe descrittiva FO+BIT di tutti i linguaggi descrivibili in una logica del primo ordine con l'aggiunta dell'operatore BIT, o alternativamente da FO(+, $\times$), o da una macchina di Turing nella gerarchia logaritmica.

Nel 1984 Furst, Saxe e Sipser dimostrarono che calcolare la parità di un'entrata non può essere decisa da nessun circuito AC⁰, anche con la non uniformità. Ne consegue che AC⁰ non è uguale a NC¹, perché una famiglia di circuiti nell'ultima classe può computare la parità. Limiti più precisi conseguono dal lemma della commutazione. Usandoli, è stato dimostrato che c'è una separazione mediante oracolo tra PH e PSPACE.

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

Collegamenti esterni

• Template:Cita libro