The strength of sharply bounded induction

DOI10.1002/malq.200610019zbMath1109.03067OpenAlexW2126270200MaRDI QIDQ3418091

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

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

Related Items (13)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ On the finite axiomatizability of ⋮ The strength of sharply bounded induction requires MSP ⋮ END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Approximate counting in bounded arithmetic ⋮ Independence results for variants of sharply bounded induction ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)

Cites Work

• Unnamed Item
• Unnamed Item

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