论文标题
零史塔兹的尺寸度折叠来自可逆卵石
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
论文作者
论文摘要
我们建立了可逆的图表卵石与卵石式配方的无效反驳之间的紧密关系，这表明可以在$ t $ t $ $ t $ s $中可逆地将$ g $在$ g $ $ g $ $ t $ t+s $ t+s $ t+s的ullstellensatz驳斥时，在时间$ t $和space $ s $中可逆地卵石$ s $ s $ s。进行反驳）。我们使用此信件来证明Nullstellensatz的许多强大度量权衡，据我们所知，这是该证明系统的第一个这样的结果。
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.
