Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-162 | 7th December 2011 15:00

A lower bound on the size of resolution proofs of the Ramsey theorem

RSS-Feed




TR11-162
Authors: Pavel Pudlak
Publication: 7th December 2011 15:00
Downloads: 3675
Keywords: 


Abstract:

We prove an exponential lower bound on the lengths of resolution proofs of propositions expressing the finite Ramsey theorem for pairs.



ISSN 1433-8092 | Imprint