The strength of sharply bounded induction

DOI10.1002/MALQ.200610019MaRDI QIDQ3418091zbMATH OpenOpenAlexFDO

Authors Emil Jeřábek

Publication date 2 February 2007

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200610019

zbMATH Keywords

bounded arithmeticpolynomial-time functionsharply bounded formula

Mathematics Subject Classification ID

Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Cited in

(16)

• Strong forward induction
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• The strength of sharply bounded induction requires MSP
• Fragments of approximate counting
• Abelian groups and quadratic residues in weak arithmetic
• The NP search problems of Frege and extended Frege proofs
• On the proof-theoretic strength of monotone induction in explicit mathematics
• On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
• Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
• Approximate counting in bounded arithmetic
• End-extensions of models of weak arithmetic from complexity-theoretic containments
• Approximate counting by hashing in bounded arithmetic
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Independence results for variants of sharply bounded induction
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Well-behaved principles alternative to bounded induction

This page was built for publication: The strength of sharply bounded induction

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