Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the proof complexity of Paris-Harrington and off-diagonal Ramsey tautologies

Autor
Carlucci, L.; Galesi, N.; Lauria, M.
Tipus d'activitat
Article en revista
Revista
ACM transactions on computational logic
Data de publicació
2016-11-01
Volum
17
Número
4
Pàgina inicial
26:1
Pàgina final
26:25
DOI
https://doi.org/10.1145/2946801 Obrir en finestra nova
URL
http://dl.acm.org/citation.cfm?doid=2996393.2946801 Obrir en finestra nova
Resum
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 Res(2). We show that under such an assumption, there is no refutation of the Paris-Harrington...
Paraules clau
Proof Complexity, Resolution, Ramsey's Theorem, Paris-harrington's Principle
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

  • Carlucci, Lorenzo  (autor)
  • Galesi, Nicola  (autor)
  • Lauria, Massimo  (autor)