All reports by Author Michele Zito:

__
TR01-079
| 6th September 2001
__

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

Michele Zito

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}})$.