# An upper bound on the space complexity of random formulae in resolution

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2002)

- Volume: 36, Issue: 4, page 329-339
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topZito, Michele. "An upper bound on the space complexity of random formulae in resolution." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.4 (2002): 329-339. <http://eudml.org/doc/245633>.

@article{Zito2002,

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\left(n \cdot \Delta ^\{-\frac\{1\}\{k-2\}\}\right)$.},

author = {Zito, Michele},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {random formulae; space complexity; satisfiability threshold; random unsatisfiable Boolean formula},

language = {eng},

number = {4},

pages = {329-339},

publisher = {EDP-Sciences},

title = {An upper bound on the space complexity of random formulae in resolution},

url = {http://eudml.org/doc/245633},

volume = {36},

year = {2002},

}

TY - JOUR

AU - Zito, Michele

TI - An upper bound on the space complexity of random formulae in resolution

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2002

PB - EDP-Sciences

VL - 36

IS - 4

SP - 329

EP - 339

AB - 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\left(n \cdot \Delta ^{-\frac{1}{k-2}}\right)$.

LA - eng

KW - random formulae; space complexity; satisfiability threshold; random unsatisfiable Boolean formula

UR - http://eudml.org/doc/245633

ER -

## References

top- [1] D. Achlioptas and G.B. Sorkin, Optimal myopic algorithms for random 3-SAT, in 41st Annual Symposium on Foundations of Computer Science (2000) 590-600. MR1931856
- [2] M. Alekhnovich, E. Ben–Sasson, A.A. Razborov and A. Wigderson, Space complexity in propositional calculus, in Proc. of the 32nd Annual ACM Symposium on Theory of Computing. Portland, OR (2000). Zbl1296.03032
- [3] P. Beame, R. Karp, T. Pitassi and M. Saks, On the complexity of unsatisfiability proofs for random $k$-CNF formulas, in Proc. of the 30th Annual ACM Symposium on Theory of Computing. New York (1998) 561-571. Zbl1028.68067MR1715604
- [4] E. Ben–Sasson and N. Galesi, Space complexity of random formulae in resolution, in Proc. of the 16th Annual IEEE Conference on Computational Complexity. IEEE Computer Society (2001). Zbl1048.03046
- [5] B. Bollobás, C. Borgs, J.T. Chayes, J.H. Kim and D.B. Wilson, The scaling window of the 2-SAT transition. Random Structures Algorithms 18 (2001) 201-256. Zbl0979.68053MR1824274
- [6] P. Cheeseman, B. Kanefsky and W.M. Taylor, Where the really hard problems are, in Proc. of IJCAI-91, edited by Kauffmann (1991) 331-337. Zbl0747.68064
- [7] V. Chvátal and E. Szemerédi, Many hard examples for resolution. J. ACM 35 (1988) 759-768. Zbl0712.03008MR1072398
- [8] S.A. Cook and R. Reckhow, The relative efficiency of propositional proof systems. J. Symb. Logic 44 (1979) 36-50. Zbl0408.03044MR523487
- [9] M. Davis, G. Logemann and D. Loveland, A machine program for theorem proving. Commun. ACM 5 (1962) 394-397. Zbl0217.54002MR149690
- [10] M. Davis and H. Putnam, A computing procedure for quantification theory. J. ACM 7 (1960) 201-215. Zbl0212.34203MR134439
- [11] J. Esteban and J.L. Toran, Space bounds for resolution, edited by C. Meinel and S. Tison, in STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 1999, Proceedings. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 551-560. Zbl0924.03020MR1734081
- [12] A. Goerdt, A threshold for unsatisfiability. J. Comput. System Sci. 53 (1996) 469-486. Zbl0870.68077MR1423858
- [13] T. Hagerup and C. Rüb, A guided tour of Chernoff bounds. Inform. Process. Lett. 33 (1989) 305-308. Zbl0702.60021MR1045520
- [14] A.C. Kaporis, L.M. Kirousis, Y.C. Stamatiou, M. Vamvakari and M. Zito, Coupon collectors, $q$-binomial coefficients and the unsatisfiability threshold, edited by A. Restivo, S. Ronchi della Rocca and L. Roversi. Theoret. Comput. Sci., in 7th Italian Conference, ICTCS 2001. Springer-Verlag, Lecture Notes in Comput. Sci. 2202 (2001) 328-338. Zbl1042.68606MR1915422
- [15] R. Bruce King, Beyond the quartic equation. Birkhauser, Boston, MA (1996). Zbl0905.12002MR1401346
- [16] R. Bruce King and E. Rodney Canfield, An algorithm for calculating the roots of a general quintic equation from its coefficients. J. Math. Phys. 32 (1991) 823-825. Zbl0741.65051MR1097764
- [17] I. Stewart, Galois Theory. Chapman and Hall, London (1973). Zbl0269.12104MR330122
- [18] J. Toran, Lower bounds for the space used in resolution, edited by J. Flum and M. Rodriguez–Artalejo, in Computer Science Logic: 13th International Workshop, CSL’99, 8th Annual Conference of the EACSL, Madrid, Spain, September 20-25, 1999, Proceedings. Springer-Verlag, Lecture Notes in Comput. Sci. 1683 (1999). Zbl0942.03010
- [19] B.L. van der Wärden, Algebra. Frederick Ungar Publishing Co., New York (1970).
- [20] R.C. Weast, Handbook of Tables for Mathematics. Cleveland: The Chemical Rubber Co. (1964). Zbl0116.10005MR175276

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.