Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > LESZEK KOLODZIEJCZYK:
All reports by Author Leszek Kolodziejczyk:

TR19-052 | 9th April 2019
Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen

Polynomial calculus space and resolution width

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 >>>




ISSN 1433-8092 | Imprint