Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
From MaRDI portal
Publication:535152
DOI10.1007/s00153-010-0220-9zbMath1231.03052MaRDI QIDQ535152
Publication date: 11 May 2011
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-010-0220-9
03F30: First-order arithmetic and fragments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strength of sharply bounded induction requires MSP
- Bootstrapping. I
- Structure and definability in general bounded arithmetic theories
- Arithmetizing uniform \(NC\)
- Bounded arithmetic and the polynomial hierarchy
- Circuits in bounded arithmetic. I
- On the bounded version of Hilbert's tenth problem
- Multifunction algebras and the provability of \(PH\downarrow\)
- Herbrandizing search problems in Bounded Arithmetic
- The strength of sharply bounded induction
- POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
- A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications
- NP search problems in low fragments of bounded arithmetic
- Fragments of bounded arithmetic and the lengths of proofs
