Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

De Rezende, Susanna F. LU orcid ; 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:
author
; ; and
organization
publishing date
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 Verlag
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
2022-04-27 00:27:35
@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 Verlag}},
  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}},
}