skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

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

Carlucci, Lorenzo ; Galesi, Nicola ; Lauria, Massimo

ACM transactions on computational logic, 2016-11, Vol.17 (4), p.1-25 [Periódico revisado por pares]

ACM

Texto completo disponível

Citações Citado por
  • Título:
    On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies
  • Autor: Carlucci, Lorenzo ; Galesi, Nicola ; Lauria, Massimo
  • Assuntos: Combinatorial analysis ; Complexity ; Graphs ; Hardness ; Lower bounds ; Paris-Harrington's principle ; Proof complexity ; Ramsey's theorem ; resolution ; Theorem proving ; Theorems ; Upper bounds
  • É parte de: ACM transactions on computational logic, 2016-11, Vol.17 (4), p.1-25
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
  • Descrição: 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.
  • Editor: ACM
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.