Some remarks on lengths of propositional proofs

DOI10.1007/BF02391554zbMath0841.03030MaRDI QIDQ1908815

Samuel R. Buss

Publication date: 16 July 1996

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

zbMATH Keywords

surveylower boundslogical flow graphsFrege proofsnumber of distinct subformulaspropositional proof lengthsequent calculus proofs

Mathematics Subject Classification ID

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

Related Items (7)

The cost of a cycle is a square ⋮ Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ Minimum propositional proof length is NP-hard to linearly approximate ⋮ Partially definable forcing and bounded arithmetic ⋮ 2002 Annual Meeting of the Association for Symbolic Logic ⋮ Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II ⋮ Substitution and Propositional Proof Complexity

Cites Work

• Exponential lower bounds for the pigeonhole principle
• Proof theory. 2nd ed
• On the number of steps in proofs
• The undecidability of \(k\)-provability
• The deduction rule and linear and near-linear proof simulations
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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