Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-142 | 21st September 2017 14:39

On small-depth Frege proofs for Tseitin for grids

RSS-Feed




TR17-142
Authors: Johan Hastad
Publication: 21st September 2017 14:39
Downloads: 175
Keywords: 


Abstract:

We prove that a small-depth Frege refutation of the Tseitin contradiction
on the grid requires subexponential size.
We conclude that polynomial size Frege refutations
of the Tseitin contradiction must use formulas of almost
logarithmic depth.



ISSN 1433-8092 | Imprint