An Upper Bound on the Space Complexity of Random Formulae in Resolution
Department of Computer Science, University of Liverpool, Chadwick Building, Peach Street, Liverpool L69 7ZF, UK;
Accepted: November 2002
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is .
Mathematics Subject Classification: 68Q25 / 03B05 / 03F20
Key words: Random formulae / space complexity / satisfiability threshold.
© EDP Sciences, 2002