Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-079 | 6th September 2001 00:00

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

TR01-079
Authors: Michele Zito
Publication: 14th November 2001 09:41
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}})$.