Circuits in bounded arithmetic. I

DOI10.1007/BF01531025MaRDI QIDQ1353986zbMATH OpenOpenAlexFDO

Authors 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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Circuit lower bounds in bounded arithmetics
• A Selection of Lower Bounds for Arithmetic Circuits
• scientific article; zbMATH DE number 1405642
• Arithmetic circuits: a survey of recent results and open questions
• On defining integers and proving arithmetic circuit lower bounds
• Bounded algebra and current-mode digital circuits
• Publication:4893147
• scientific article; zbMATH DE number 1344922
• Lower bounds on arithmetic circuits via partial derivatives
• Arithmetic and Algebraic Circuits

Cites work

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

Cited in

(6)

• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• On defining integers and proving arithmetic circuit lower bounds
• Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
• Independence results for variants of sharply bounded induction
• A lower bound for primality
• Bounded algebra and current-mode digital circuits

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1353986)