scientific article; zbMATH DE number 2196511

MaRDI QIDQ5465358zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 22 August 2005

zbMATH Keywords

bounded depth Frege systemsfragments of bounded arithmeticParis-Wilkie translationPK-proof systems

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Cut-elimination and normal-form theorems (03F05) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Bounded arithmetic in free logic
• On the provability logic of bounded arithmetic
• Logic of Proofs for Bounded Arithmetic
• scientific article; zbMATH DE number 1070621
• Approximation and Small-Depth Frege Proofs
• Axiomatizing proof tree concepts in bounded arithmetic
• scientific article; zbMATH DE number 819737
• Bounded arithmetic, proof complexity and two papers of Parikh
• Fragments of bounded arithmetic and the lengths of proofs
• Theories for subexponential-size bounded-depth Frege proofs

Cited in

(9)

• Bounded arithmetic, proof complexity and two papers of Parikh
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Hard examples for the bounded depth Frege proof system
• A bounded arithmetic AID for Frege systems
• Approximation and Small-Depth Frege Proofs
• From positive and intuitionistic bounded arithmetic to monotone proof complexity
• Nested PLS
• On the computational complexity of cut-reduction
• The bounded proof property via step algebras and step frames

This page was built for publication:

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