No CrossRef data available.
Article contents
An Upper Bound on the Space Complexity of Random Formulae in Resolution
Published online by Cambridge University Press: 15 February 2003
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 = Δn clauses is $O\left(n \cdot \Delta^{-\frac{1}{k-2}}\right)$.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 36 , Issue 4 , October 2002 , pp. 329 - 339
- Copyright
- © EDP Sciences, 2002