Polynomially and superexponentially shorter proofs in fragments of arithmetic

DOI10.2307/2275435zbMATH Open0765.03029OpenAlexW2039356064MaRDI QIDQ4032866FDOQ4032866

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

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

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)

Cites Work

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

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
• On mathematical instrumentalism
• Title not available (Why is that?)
• Short proofs for slow consistency
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)