Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-079 | 6th September 2001 00:00

An Upper Bound on the Space Complexity of Random Formulae in Resolution

RSS-Feed




TR01-079
Authors: Michele Zito
Publication: 14th November 2001 09:41
Downloads: 1269
Keywords: 


Abstract:

We prove that, with high probability, the space complexity of refuting
a random unsatisfiable boolean formula in $k$-CNF on $n$
variables and $m = \Delta n$ clauses is
$O(n \cdot \Delta^{-\frac{1}{k-2}})$.



ISSN 1433-8092 | Imprint