Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
De Rezende, Susanna F. LU
; Meir, Or
; Nordström, Jakob
LU
and Robere, Robert
(2021)
In Computational Complexity
30(1).
- Abstract
We establish an exactly tight relation between reversiblepebblings of graphs and Nullstellensatz refutations of pebbling formulas,showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formulaover G in size t + 1 and degree s (independently of the field in whichthe Nullstellensatz refutation is made). We use this correspondenceto prove a number of strong size-degree trade-offs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/7753e6c2-4708-4f26-99ee-54f9eab914ff
- author
- De Rezende, Susanna F.
LU
; Meir, Or
; Nordström, Jakob
LU
and Robere, Robert
- organization
- publishing date
- 2021
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- 68Q17, Nullstellensatz, Pebbling, Proof complexity, Trade-offs
- in
- Computational Complexity
- volume
- 30
- issue
- 1
- article number
- 4
- publisher
- Birkhäuser
- external identifiers
-
- scopus:85101029418
- ISSN
- 1016-3328
- DOI
- 10.1007/s00037-020-00201-y
- language
- English
- LU publication?
- yes
- id
- 7753e6c2-4708-4f26-99ee-54f9eab914ff
- date added to LUP
- 2021-03-01 08:47:30
- date last changed
- 2024-08-08 12:46:07
@article{7753e6c2-4708-4f26-99ee-54f9eab914ff,
abstract = {{<p>We establish an exactly tight relation between reversiblepebblings of graphs and Nullstellensatz refutations of pebbling formulas,showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formulaover G in size t + 1 and degree s (independently of the field in whichthe Nullstellensatz refutation is made). We use this correspondenceto prove a number of strong size-degree trade-offs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.</p>}},
author = {{De Rezende, Susanna F. and Meir, Or and Nordström, Jakob and Robere, Robert}},
issn = {{1016-3328}},
keywords = {{68Q17; Nullstellensatz; Pebbling; Proof complexity; Trade-offs}},
language = {{eng}},
number = {{1}},
publisher = {{Birkhäuser}},
series = {{Computational Complexity}},
title = {{Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling}},
url = {{http://dx.doi.org/10.1007/s00037-020-00201-y}},
doi = {{10.1007/s00037-020-00201-y}},
volume = {{30}},
year = {{2021}},
}