Circuits in bounded arithmetic. I
From MaRDI portal
Publication:1353986
DOI10.1007/BF01531025zbMath0865.03046MaRDI QIDQ1353986
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
03D15: Complexity of computation (including implicit computational complexity)
03F30: First-order arithmetic and fragments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A lower bound for primality, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), Independence results for variants of sharply bounded induction, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
Cites Work