Some remarks on lengths of propositional proofs

DOI10.1007/BF02391554MaRDI QIDQ1908815zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 16 July 1996

Published in Archive for Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

surveylower boundsFrege proofslogical flow graphsnumber of distinct subformulaspropositional proof lengthsequent calculus proofs

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 1223616
• Approximation and Small-Depth Frege Proofs
• scientific article; zbMATH DE number 1390276
• Propositional proofs in Frege and extended Frege systems (abstract)

Cites work

• scientific article; zbMATH DE number 440475 (Why is no real title available?)
• scientific article; zbMATH DE number 4104947 (Why is no real title available?)
• scientific article; zbMATH DE number 3687372 (Why is no real title available?)
• scientific article; zbMATH DE number 3583767 (Why is no real title available?)
• scientific article; zbMATH DE number 806745 (Why is no real title available?)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• On the number of steps in proofs
• Polynomial size proofs of the propositional pigeonhole principle
• Proof theory. 2nd ed
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The deduction rule and linear and near-linear proof simulations
• The relative efficiency of propositional proof systems
• The undecidability of k-provability

Cited in

(12)

• Substitution and Propositional Proof Complexity
• scientific article; zbMATH DE number 440475 (Why is no real title available?)
• On the number of steps in proofs
• Partially definable forcing and bounded arithmetic
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• scientific article; zbMATH DE number 2079024 (Why is no real title available?)
• scientific article; zbMATH DE number 3952747 (Why is no real title available?)
• Minimum propositional proof length is NP-hard to linearly approximate
• 2002 Annual Meeting of the Association for Symbolic Logic
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• The cost of a cycle is a square
• Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II

This page was built for publication: Some remarks on lengths of propositional proofs

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