EUVIMEDEUVIMED entdecken
Crossref

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

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →