Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-052 | 9th April 2019 18:34

#### Polynomial calculus space and resolution width

TR19-052
Authors: Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen
Publication: 9th April 2019 19:02
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 the first analogue, in polynomial calculus, of Atserias and Dalmau's result lower-bounding clause space in resolution by resolution width.