Circuits in bounded arithmetic. I

DOI10.1007/BF01531025zbMath0865.03046OpenAlexW1964621816MaRDI QIDQ1353986

Spyro-Giorgio Mantzivis

Publication date: 13 May 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01531025

zbMATH Keywords

bounded arithmeticpolynomial size circuit familiespolynomial time computable

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ A lower bound for primality ⋮ Independence results for variants of sharply bounded induction ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)

Cites Work

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

This page was built for publication: Circuits in bounded arithmetic. I