Bootstrapping. I

DOI10.1016/j.apal.2009.03.004zbMath1225.03048OpenAlexW2005505967MaRDI QIDQ636291

Sedki Boughattas, Jean-Pierre Ressayre

Publication date: 26 August 2011

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

Full work available at URL: https://doi.org/10.1016/j.apal.2009.03.004

zbMATH Keywords

nonstandard modelsweak arithmeticscomplexity classescounterfeiting integers

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Nonstandard models of arithmetic (03H15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Restricted polynomial induction versus ordinary induction ⋮ Real closures of models of weak arithmetic ⋮ On the finite axiomatizability of ⋮ The strength of sharply bounded induction requires MSP ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Independence results for variants of sharply bounded induction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subsystems of true arithmetic and hierarchies of functions
• Structure and definability in general bounded arithmetic theories
• Rapidly growing Ramsey functions
• Set theory. An introduction to large cardinals
• Polynomial time uniformization and non-standard methods
• Subtle cardinals and linear orderings
• Well-behaved principles alternative to bounded induction
• Arithmetization of the field of reals with exponentiation extended abstract
• L'arithmétique ouverte et ses modèles non-standards
• Models with compactness properties relative to an admissible language
• A model theoretic proof of a subexponential time witnessing theorem
• L'Induction Ouverte Dans Les Anneaux Discrets Ordonnes et Normaux N'est pas Finiment Axiomatisable
• Trois theoremes sur l'induction pour les formules ouvertes munies de l'exponentielle