Revised: May 26, 2022
Published: September 15, 2025
Abstract: [Plain Text Version]
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 that, in resolution, width is a lower bound on clause space.
As a by-product of our new approach to space lower bounds we give a simple proof of Bonacina's recent result that total space in resolution (the total number of variable occurrences that must be kept in memory) is at least the width squared.
As corollaries of the main result we obtain some new lower bounds on the PCR space needed to refute specific formulas, as well as partial answers to some open problems about relations between space, size, and degree for polynomial calculus.
--------------
A conference version of this paper appeared in the Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS'19).
Licensed under a Creative Commons Attribution License (CC-BY)