Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)

DOI10.1007/s00153-010-0220-9zbMath1231.03052OpenAlexW2031918097MaRDI QIDQ535152

Chris Pollett

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

zbMATH Keywords

bounded arithmeticindependence resultsfunction algebrasweak fragments

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

This page was built for publication: Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)