A Note on Conservativity Relations among Bounded Arithmetic Theories

DOI<375::AID-MALQ375>3.0.CO;2-L 10.1002/1521-3870(200204)48:3<375::AID-MALQ375>3.0.CO;2-LzbMath0997.03046OpenAlexW2028861313MaRDI QIDQ4530148

Jan Krajíček, Russell Impagliazzo

Publication date: 29 May 2002

Full work available at URL: https://doi.org/10.1002/1521-3870(200204)48:3<375::aid-malq375>3.0.co;2-l

zbMATH Keywords

bounded arithmeticconstant depth Frege systems

Mathematics Subject Classification ID

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

Related Items

The Ordering Principle in a Fragment of Approximate Counting ⋮ Towards NP-P via proof complexity and search ⋮ Short refutations for an equivalence‐chain principle for constant‐depth formulas ⋮ The canonical pairs of bounded depth Frege systems ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Random resolution refutations

Cites Work

• Unnamed Item