A lower bound on the size of resolution proofs of the Ramsey theorem

DOI10.1016/J.IPL.2012.05.004MaRDI QIDQ436623zbMATH OpenOpenAlexFDO

Authors Pavel Pudlák

Publication date 25 July 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.05.004

zbMATH Keywords

computational complexityRamsey theoremresolution proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Cites work

• scientific article; zbMATH DE number 512985 (Why is no real title available?)
• A note on propositional proof complexity of some Ramsey-type statements
• On the weak pigeonhole principle

Cited in

(6)

• Co-Nondeterminism in Compositions
• Resolution with counting: dag-like lower bounds and different moduli
• Formalizing finite Ramsey theory in Lean 4
• A fixed-depth size-hierarchy theorem for AC ⁰ [⊕] via the coin problem
• An Introduction to Lower Bounds on Resolution Proof Systems
• scientific article; zbMATH DE number 7650367 (Why is no real title available?)

This page was built for publication: A lower bound on the size of resolution proofs of the Ramsey theorem

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