Structure and definability in general bounded arithmetic theories

DOI10.1016/S0168-0072(99)00008-1zbMath0935.03070OpenAlexW2160804094MaRDI QIDQ1125060

Chris Pollett

Publication date: 9 May 2000

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(99)00008-1

zbMATH Keywords

inductiondefinabilityconservativitybounded arithmetic theories

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Related Items (16)

Well-behaved principles alternative to bounded induction ⋮ Circuit principles and weak pigeonhole variants ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ Restricted polynomial induction versus ordinary induction ⋮ Preservation theorems and restricted consistency statements in bounded arithmetic ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ On the finite axiomatizability of ⋮ Bootstrapping. I ⋮ On the computational complexity of cut-reduction ⋮ \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ Consequences of the provability of NP ⊆ P/poly ⋮ A Characterisation of Definable NP Search Problems in Peano Arithmetic ⋮ Multifunction algebras and the provability of \(PH\downarrow\) ⋮ Models of replacement schemes

This page was built for publication: Structure and definability in general bounded arithmetic theories