Sökning: (WFRF:(Jakob Robert)) srt2:(2020-2022) >
Nullstellensatz Siz...
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
-
- De Rezende, Susanna F. (författare)
- Institute of Mathematics of the Academy of Sciences of the Czech Republic
-
- Meir, Or (författare)
- University of Haifa
-
- Nordström, Jakob (författare)
- 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
-
visa fler...
-
- Robere, Robert (författare)
- McGill University
-
visa färre...
-
(creator_code:org_t)
- 2021-02-12
- 2021
- Engelska.
-
Ingår i: Computational Complexity. - : Springer Science and Business Media LLC. - 1016-3328 .- 1420-8954. ; 30:1
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://drops.dagstu...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- 68Q17
- Nullstellensatz
- Pebbling
- Proof complexity
- Trade-offs
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas