Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-146 | 6th November 2014 15:06

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


Authors: Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan
Publication: 6th November 2014 15:26
Downloads: 904


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 space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random $3$-CNF $\phi$ in $n$ variables requires, with high probability, $\Omega(n/\log n)$ distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution refutation $\phi$ requires, with high probability, $\Omega(n/\log n)$ clauses each of width $\Omega(n/\log n)$ to be kept at the same time in memory. This gives a $\Omega(n^2/\log^2 n)$ lower bound for the total space needed in Resolution to refute $\phi$.
The main technical innovation is a variant of Hall's theorem.
We show that in bipartite graphs $G$ with bipartition $(L,R)$ and left-degree at most 3, $L$ can be covered by certain families of disjoint paths, called $(2,4)$-matchings, provided that $L$ expands in $R$ by a factor of $(2-\epsilon)$, for $\epsilon < \frac{1}{23}$.

ISSN 1433-8092 | Imprint