Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)

DOI10.1016/0020-0190(94)00036-0zbMath0807.68032OpenAlexW2095458980MaRDI QIDQ1327317

Sorin Istrail, Dejan Živković

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

zbMATH Keywords

circuit complexitycomplexity classesBoolean formulas

Mathematics Subject Classification ID

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

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Parity, circuits, and the polynomial-time hierarchy
• Unnamed Item

This page was built for publication: Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\)