Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with paris-harrington:
TR10-153 | 7th October 2010
Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

Paris-Harrington tautologies

Revisions: 2

We initiate the study of the proof complexity of propositional encoding of (weak cases of) concrete independence results. In particular we study the proof complexity of Paris-Harrington's Large Ramsey Theorem. We prove a conditional lower bound in Resolution and a quasipolynomial upper bound in bounded-depth Frege.

more >>>

ISSN 1433-8092 | Imprint