文章基本信息

标题：Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
本地全文：下载
作者：Susanna F. de Rezende ; Jakob Nordstr{"o}m ; Or Meir 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：137
页码：1-16
DOI：10.4230/LIPIcs.CCC.2019.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：proof complexity; Nullstellensatz; pebble games; trade-offs; size; degree