Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with random 3CNFs:
TR14-146 | 6th November 2014
Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

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

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 ... more >>>

ISSN 1433-8092 | Imprint