A Note on Conservativity Relations among Bounded Arithmetic Theories

DOI10.1002/1521-3870(200204)48:3%3C375::AID-MALQ375%3E3.0.CO;2-LMaRDI QIDQ4530148zbMATH OpenOpenAlexFDO

Authors Russell Impagliazzo, Jan Krajíček

Publication date 29 May 2002

Full work available at URL https://doi.org/10.1002/1521-3870(200204)48:3%3C375::aid-malq375%3E3.0.co;2-l

zbMATH Keywords

bounded arithmeticconstant depth Frege systems

Mathematics Subject Classification ID

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

Cited in

(12)

• The canonical pairs of bounded depth Frege systems
• A generalization of a conservativity theorem for classical versus intuitionistic arithmetic
• Towards NP-P via proof complexity and search
• Existentially Closed Models and Conservation Results in Bounded Arithmetic
• Structure and definability in general bounded arithmetic theories
• Incompleteness in the finite domain
• scientific article; zbMATH DE number 4145897 (Why is no real title available?)
• The ordering principle in a fragment of approximate counting
• scientific article; zbMATH DE number 218509 (Why is no real title available?)
• Short refutations for an equivalence-chain principle for constant-depth formulas
• Depth-d Frege systems are not automatable unless P\,=\,NP
• Random resolution refutations

This page was built for publication: A Note on Conservativity Relations among Bounded Arithmetic Theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4530148)