AC0
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Nota_disambigua.svg/18px-Nota_disambigua.svg.png)
AC0 è 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).[1] Essa perciò contiene NC0, che ha soltanto porte AND e OR con numero massimo di linee d'ingresso limitato.[2]
Da un punto di vista della complessità descrittiva, AC0 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(+, ), o da una macchina di Turing nella gerarchia logaritmica.[3]
Nel 1984 Furst, Saxe e Sipser dimostrarono che calcolare la parità di un'entrata non può essere decisa da nessun circuito AC0, anche con la non uniformità.[4][5] Ne consegue che AC0 non è uguale a NC1, perché una famiglia di circuiti nell'ultima classe può computare la parità.[1] 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 AC0, ma la moltiplicazione no (almeno, non in base alle abituali rappresentazioni binarie o in base 10 degli interi).
Note
- ^ a b Arora & Barak (2009) p. 118
- ^ Arora & Barak (2009) p. 117
- ^ Neil Immerman, Descriptive complexity, New York, Springer-Verlag, 1999, p. 85, ISBN 9780387986005.
- ^ Merrick Furst, James B. Saxe e Michael Sipser, Parity, circuits, and the polynomial-time hierarchy, in Math. Syst. Theory, vol. 17, 1984, pp. 13–27, ISSN 0025-5661 (WC · ACNP), Zbl 0534.94008.
- ^ Arora & Barak (2009) p. 287
Collegamenti esterni
- Sanjeev Arora e Boaz Barak, Computational complexity. A modern approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4, Zbl 1193.68112.
V · D · M | |
---|---|
P · NP · co-NP · NP-C · co-NP-C · NP-hard · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · Co-RE · RE-C · Co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)