On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
Ilario Bonacina, Marı́a Luisa Bonet · 2022
We characterize the strength of the algebraic proof systems Sherali-Adams () and Nullstellensatz () in terms of Frege-style proof systems. Unlike bounded-depth Frege, has polynomial-size proofs of the pigeonhole principle (). A natural question is whether adding to bounded-depth Frege is enough to simulate .