Some remarks on lengths of propositional proofs
From MaRDI portal
Publication:1908815
DOI10.1007/BF02391554zbMath0841.03030MaRDI QIDQ1908815
Publication date: 16 July 1996
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
surveylower boundslogical flow graphsFrege proofsnumber of distinct subformulaspropositional proof lengthsequent calculus proofs
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