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

 Access to full text

 Full (PDF)

1. [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. [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. [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. [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. [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. [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. [7] V. Chvátal and E. Szemerédi, Many hard examples for resolution. J. ACM 35 (1988) 759-768. Zbl0712.03008MR1072398
8. [8] S.A. Cook and R. Reckhow, The relative efficiency of propositional proof systems. J. Symb. Logic 44 (1979) 36-50. Zbl0408.03044MR523487
9. [9] M. Davis, G. Logemann and D. Loveland, A machine program for theorem proving. Commun. ACM 5 (1962) 394-397. Zbl0217.54002MR149690
10. [10] M. Davis and H. Putnam, A computing procedure for quantification theory. J. ACM 7 (1960) 201-215. Zbl0212.34203MR134439
11. [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. [12] A. Goerdt, A threshold for unsatisfiability. J. Comput. System Sci. 53 (1996) 469-486. Zbl0870.68077MR1423858
13. [13] T. Hagerup and C. Rüb, A guided tour of Chernoff bounds. Inform. Process. Lett. 33 (1989) 305-308. Zbl0702.60021MR1045520
14. [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. [15] R. Bruce King, Beyond the quartic equation. Birkhauser, Boston, MA (1996). Zbl0905.12002MR1401346
16. [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. [17] I. Stewart, Galois Theory. Chapman and Hall, London (1973). Zbl0269.12104MR330122
18. [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. [19] B.L. van der Wärden, Algebra. Frederick Ungar Publishing Co., New York (1970). 
20. [20] R.C. Weast, Handbook of Tables for Mathematics. Cleveland: The Chemical Rubber Co. (1964). Zbl0116.10005MR175276