Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC^0
Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC^0
Autori:
Časopis: Information Processing Letters
Volume, no: 50 , 4
ISSN: 0020-0190
DOI: 10.1016/0020-0190(94)00036-0
Stranice: 211-216
Link: https://www.sciencedirect.com/science/article/abs/pii/0020019094000360?via%3Dihub
Apstrakt:
We show that the complexity classes AC^0 and NC^1 consist exactly of, respectively, constant and O(log n) width polynomial-size Boolean formulas.
Ključne reči: Computational complexity, Boolean functions, Circuit complexity
Kategorije objave:
Bibliografske reference nastavnika Univerziteta Singidunum
Zahvaljujemo se što ste preuzeli publikaciju sa portala Singipedia.
Ukoliko želite da se prijavite za obaveštenja o sadržajima iz oblasti ove publikacije, možete nam ostaviti adresu svoje elektronske pošte.