On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies
ACM Transactions on Computational Logic · 2016-11-15 · 17 (4) · 1-25
DOI: 10.1145/2946801 ↗At a glance
Journal article in ACM Transactions on Computational Logic, published online on 2016-09-10. Written by Lorenzo Carlucci and 2 co-authors. Cited 1 times so far (Crossref); 25 references. Funded by: Limits of Theorem Proving, John Templeton Foundation.
Abstract (original language)
We study the proof complexity of Paris-Harrington’s Large Ramsey Theorem for bi-colorings of graphs and of off-diagonal Ramsey’s Theorem. For Paris-Harrington, we prove a non-trivial conditional lower bound in Resolution and a non-trivial upper bound in bounded-depth Frege. The lower bound is conditional on a (very reasonable) hardness assumption for a weak (quasi-polynomial) Pigeonhole principle in R es (2). We show that under such an assumption, there is no refutation of the Paris-Harrington formulas of size quasi-polynomial in the number of propositional variables. The proof technique for the lower bound extends the idea of using a combinatorial principle to blow up a counterexample for another combinatorial principle beyond the threshold of inconsistency. A strong link with the proof complexity of an unbalanced off-diagonal Ramsey principle is established. This is obtained by adapting some constructions due to Erdős and Mills. We prove a non-trivial Resolution lower bound for a family of such off-diagonal Ramsey principles.
Funding
- Limits of Theorem Proving
- John Templeton Foundation
Cite
APA
Carlucci, L., Galesi, N., & Lauria, M. (2016). On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies. ACM Transactions on Computational Logic, 17(4), 1-25. https://doi.org/10.1145/2946801
Vancouver
Carlucci L, Galesi N, Lauria M. On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies. ACM Transactions on Computational Logic. 2016;17(4):1-25. doi:10.1145/2946801
BibTeX
@article{Carlucci2016,
author = {Carlucci, Lorenzo and Galesi, Nicola and Lauria, Massimo},
title = {On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies},
journal = {ACM Transactions on Computational Logic},
year = {2016},
volume = {17},
number = {4},
pages = {1--25},
doi = {10.1145/2946801}
}
EUVIMED