scientific article; zbMATH DE number 2079024

MaRDI QIDQ4474836zbMATH OpenFDO

Authors Pavel Pudlák, Samuel R. Buss

Publication date 21 July 2004

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1390276
• On lengths of proofs in non-classical logics
• scientific article; zbMATH DE number 3313427
• The Complexity of Propositional Proofs
• Some remarks on lengths of propositional proofs

Cited in

(12)

• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• Proof complexity of monotone branching programs
• Expander construction in \(\mathrm{VNC}^1\)
• A game characterisation of tree-like Q-resolution size
• A combinatorial characterization of resolution width
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• Expander construction in \(\mathsf{VNC}^1\)
• Generalisation of proof simulation procedures for Frege systems by M. L. Bonet and S. R. Buss
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
• Proof complexity of positive branching programs
• Prover-adversary games for systems over (non-deterministic) branching programs

This page was built for publication:

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