2026-08-10T18:26:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10840 2024-03-06T10:46:50Z ddc:004 open_access

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling de Rezende, Susanna F. Nordström, Jakob Meir, Or Robere, Robert proof complexity Nullstellensatz pebble games trade-offs size degree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanna F. de Rezende and Jakob Nordström and Or Meir and Robert Robere 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.18 urn:nbn:de:0030-drops-108403 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode