On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies
ACM Transactions on Computational Logic · 15.11.2016 · 17 (4) · 1-25
DOI: 10.1145/2946801 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 10.09.2016. Verfasst von Lorenzo Carlucci und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: Limits of Theorem Proving, John Templeton Foundation.
Abstract (Originalsprache)
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.
Förderung
- Limits of Theorem Proving
- John Templeton Foundation
Zitieren
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