Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)
From MaRDI portal
Publication:1327317
DOI10.1016/0020-0190(94)00036-0zbMath0807.68032OpenAlexW2095458980MaRDI QIDQ1327317
Publication date: 1 March 1995
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)00036-0
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ A constant-space sequential model of computation for first-order logic ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ A constant-space sequential model of computation for first-order logic
Cites Work
This page was built for publication: Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)