Polynomial calculus space and resolution width

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00518434" target="_blank" >RIV/67985840:_____/19:00518434 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1109/FOCS.2019.00081" target="_blank" >http://dx.doi.org/10.1109/FOCS.2019.00081</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/FOCS.2019.00081" target="_blank" >10.1109/FOCS.2019.00081</a>

Result language

angličtina

Original language name

Polynomial calculus space and resolution width

Original language description

We show that if a k-CNF requires width w to refute in resolution, then it requires space √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. 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 lower-bounded by 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA19-05497S" target="_blank" >GA19-05497S: Complexity of mathematical proofs and structures</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

60th Annual Symposium on Foundations of Computer Science (FOCS)

ISBN

978-1-7281-4952-3

ISSN

0272-5428

e-ISSN

—

Number of pages

13

Pages from-to

1325-1337

Publisher name

IEEE

Place of publication

Piscataway

Event location

Baltimore

Event date

Nov 9, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000510015300072