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

DOI10.1016/J.IPL.2012.05.004zbMATH Open1243.68187OpenAlexW1993227745MaRDI QIDQ436623FDOQ436623

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

• On the weak pigeonhole principle
• Title not available (Why is that?)
• A note on propositional proof complexity of some Ramsey-type statements

Cited In (7)

• A fixed-depth size-hierarchy theorem for AC ⁰ [⊕] via the coin problem
• An Introduction to Lower Bounds on Resolution Proof Systems
• Resolution with counting: dag-like lower bounds and different moduli
• Formalizing finite Ramsey theory in Lean 4
• The complexity of proving that a graph is Ramsey
• Co-Nondeterminism in Compositions
• Title not available (Why is that?)

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)