Space proof complexity for random 3-CNFs

Patrick Bennett, Ilario Bonacina, Nicola Galesi +3

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random $3$-CNF…