On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies

DOI10.1145/2946801zbMath1407.03073OpenAlexW2518743604WikidataQ61732577 ScholiaQ61732577MaRDI QIDQ5278196

Massimo Lauria, Nicola Galesi, Lorenzo Carlucci

Publication date: 13 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11573/902288

zbMATH Keywords

resolutionRamsey's theoremproof complexityParis-Harrington's principle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Generalized Ramsey theory (05C55) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• A note on propositional proof complexity of some Ramsey-type statements
• Ramsey-Paris-Harrington numbers for graphs
• A note on Ramsey numbers
• Some bounds for the Ramsey-Paris-Harrington numbers
• Rapidly growing Ramsey functions
• Asymptotic lower bounds for Ramsey functions
• Cutting plane and Frege proofs
• Separation results for the size of constant-depth propositional proofs
• On the weak pigeonhole principle
• Graph Theory and Probability. II
• Approximation and Small-Depth Frege Proofs
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Lower bounds to the size of constant-depth propositional proofs
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Some graph theoretic results associated with Ramsey's theorem
• A new proof of the weak pigeonhole principle
• Concentration of Measure for the Analysis of Randomized Algorithms