文章基本信息

标题：Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
本地全文：下载
作者：Or Meir ; Jakob Nordström ; Robert Robere 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-23
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We establish an exactly tight relation between reversible pebblings 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 formula over G in size t 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.