[Proof Complexity] New preprint

Neil Thapen thapen at math.cas.cz
Wed Oct 15 19:32:18 CEST 2014

Dear colleagues,

A new preprint, "A trade-off between length and width in resolution" is 
available at http://users.math.cas.cz/~thapen/length_width.pdf
Any comments or corrections are welcome.

The abstract is: We describe a family of CNF formulas in n variables, with
small initial width, which have polynomial length resolution refutations.
By a result of Ben-Sasson and Wigderson it follows that they must also
have narrow resolution refutations, of width O(\sqrt{nlogn}). We show 
that, for our formulas, this decrease in width comes at the expense of an 
increase in size, and any such narrow refutations must have exponential 



More information about the Proof-Complexity mailing list