Search: onr:"swepub:oai:lup.lub.lu.se:7753e6c2-4708-4f26-99ee-54f9eab914ff" >
Nullstellensatz Siz...
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
-
- De Rezende, Susanna F. (author)
- Institute of Mathematics of the Academy of Sciences of the Czech Republic
-
- Meir, Or (author)
- University of Haifa
-
- Nordström, Jakob (author)
- Lund University,Lunds universitet,Parallella System,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Parallel Systems,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH,University of Copenhagen
-
show more...
-
- Robere, Robert (author)
- McGill University
-
show less...
-
(creator_code:org_t)
- 2021-02-12
- 2021
- English.
-
In: Computational Complexity. - : Springer Science and Business Media LLC. - 1016-3328 .- 1420-8954. ; 30:1
- Related links:
-
http://dx.doi.org/10...
-
show more...
-
https://drops.dagstu...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- 68Q17
- Nullstellensatz
- Pebbling
- Proof complexity
- Trade-offs
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database