Polynomially and superexponentially shorter proofs in fragments of arithmetic

DOI10.2307/2275435MaRDI QIDQ4032866zbMATH OpenOpenAlexFDO

Authors Franco Montagna

Publication date 1 April 1993

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275435

zbMATH Keywords

modal logicprovability logicfragments of arithmeticspeed-uplengths of proofs

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40)

Recommendations

• Fragments of bounded arithmetic and the lengths of proofs
• scientific article; zbMATH DE number 4010488
• Tractable fragments of Presburger arithmetic
• The polynomial bounds of proof complexity in Frege systems
• Polynomial induction and length minimization in intuitionistic bounded arithmetic
• scientific article; zbMATH DE number 1361469
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• scientific article; zbMATH DE number 6387509
• Cutting-plane proofs in polynomial space
• An exponential lower bound for proofs in focused calculi

Cites work

• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 1032008 (Why is no real title available?)
• Much Shorter Proofs
• On the number of steps in proofs
• On the scheme of induction for bounded arithmetic formulas
• Preface for Studia Logica special issue (2)
• Provability interpretations of modal logic
• Provable Fixed Points
• Rosser sentences
• Sentences undecidable in formalized arithmetic. An exposition of the theory of Kurt Gödel
• The modal logic of provability. The sequential approach

Cited in

(13)

• On the Rabin's speed-up of proofs for some systems of first order logic
• Two recursion theoretic characterizations of proof speed-ups
• Non-elementary speed-ups in logic calculi
• scientific article; zbMATH DE number 815105 (Why is no real title available?)
• On mathematical instrumentalism
• Short proofs for slow consistency
• scientific article; zbMATH DE number 15882 (Why is no real title available?)
• Tractable fragments of Presburger arithmetic
• Unbounded Proof-Length Speed-Up in Deduction Modulo
• Polynomial induction and length minimization in intuitionistic bounded arithmetic
• Obituary: Franco Montagna (1948--2015)
• Much shorter proofs: A bimodal investigation
• scientific article; zbMATH DE number 440480 (Why is no real title available?)

This page was built for publication: Polynomially and superexponentially shorter proofs in fragments of arithmetic

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