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

DOI10.1016/j.ipl.2012.05.004zbMath1243.68187OpenAlexW1993227745MaRDI QIDQ436623

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)

Related Items (2)

The complexity of proving that a graph is Ramsey ⋮ An Introduction to Lower Bounds on Resolution Proof Systems

Cites Work

• A note on propositional proof complexity of some Ramsey-type statements
• On the weak pigeonhole principle
• Unnamed Item

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