Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-182 | 30th December 2021 21:15

On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems

RSS-Feed




TR21-182
Authors: Ilario Bonacina, Maria Luisa Bonet
Publication: 30th December 2021 22:42
Downloads: 465
Keywords: 


Abstract:

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems the following way. We show that SA (resp. NS over ${\bf Z}$) with unary coefficients lies strictly between tree-like resolution and tree-like depth-$1$ Frege + PHP (resp. ofPHP). We introduce weighted versions of PHP and ofPHP, resp. wtPHP and of-wtPHP and we show that SA (resp. NS over ${\bf Z}$) lies strictly between resolution and tree-like depth-$1$ Frege + wtPHP (resp. of-wtPHP). We also show analogue results for depth-$d$ versions of SA and NS.



ISSN 1433-8092 | Imprint