Space proof complexity for random $3$-CNFs via a $(2-\epsilon )$-Hall's Theorem

Ilario Bonacina, Nicola Galesi, Tony Huynh +1

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total…