__
TR01-079 | 6th September 2001 00:00
__

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

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