EUVIMEDObjevte EUVIMED
Crossref

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

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

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.

AbstraktBibliografické údajeCiteRelated studies

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}
}
Start for free →