All reports by Author Leszek Kolodziejczyk:

__
TR19-052
| 9th April 2019
__

Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen#### Polynomial calculus space and resolution width

Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen

We show that if a $k$-CNF requires width $w$ to refute in resolution, then it requires space $\sqrt w$ to refute in polynomial calculus, where the space of a polynomial calculus refutation is the number of monomials that must be kept in memory when working through the proof. This is ... more >>>