On meta complexity of propositional formulas and propositional proofs

DOI10.1007/s00153-008-0068-4zbMath1148.03037OpenAlexW2045675862MaRDI QIDQ937212

Pavel Naumov

Publication date: 20 August 2008

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

Full work available at URL: https://doi.org/10.1007/s00153-008-0068-4

zbMATH Keywords

proof complexityBoolean recursionspropositional systems

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• On the complexity of cutting-plane proofs
• Exponential lower bounds for the pigeonhole principle
• The intractability of resolution
• The relative efficiency of propositional proof systems
• Diagonalization in proof complexity
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Implicit proofs
• Some Results on the Length of Proofs

This page was built for publication: On meta complexity of propositional formulas and propositional proofs