.png){kind=icon}
.png){kind=icon}
Return
Polynomial Calculus Space and Resolution Width
.png){kind=icon}
OA
AI
DOI：10.4086/toc.2025.v021a006.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We show that if a k-CNF requires width w to refute in resolution, then it requires space root 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.
Keywords:
proof complexity
resolution
polynomial calculus
space
width
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
T
IF:
0.7
Papers:
10
Citations:
0
Organization
No organization information available