A probabilistic analysis of a new satisfiability algorithm
Apolloni, B. ; Di Gregorio, S.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982), p. 201-223 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1982-01-01
@article{ITA_1982__16_3_201_0,
     author = {Apolloni, B. and Di Gregorio, S.},
     title = {A probabilistic analysis of a new satisfiability algorithm},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {16},
     year = {1982},
     pages = {201-223},
     mrnumber = {686913},
     zbl = {0489.68038},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1982__16_3_201_0}
}

Apolloni, B.; Di Gregorio, S. A probabilistic analysis of a new satisfiability algorithm. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) pp. 201-223. http://gdmltest.u-ga.fr/item/ITA_1982__16_3_201_0/

1. K. J. Astrom, Introduction to Stochastic Control Theory, NewYork, London, Academic Press, 1970. | MR 270799 | Zbl 0226.93027

2. D. E. Barton and F. N. David, Combinatorial Chance, London, Griffin, 1972.

3. A. T. Bharuka-Reid, Elements of the Theory of Markov Processes and their Applications, London, McGraw-Hill, 1960. | MR 112177 | Zbl 0095.32803

4. S. A. Cook, The Complexity of Theorem-Proving Procedures, Proc. third A.C.M. Symposium on Theory of Computing, 1971, pp. 151-158. | Zbl 0253.68020

5. H. Kramer, Mathematical Methods of Statistics, Princeton, Princeton University Press, 1945. | Zbl 0063.01014

6. Z. Galil, On Enumeration Procedures for Theorem Proving and for Integer Programming, Automata Languages and Programming Third International Colloquim, S. MICHAELSON and R. MILNER, Eds., Edinburg University Press, 1976, pp. 355-381. | Zbl 0358.68132

7. M. R. Garey and D. S. Johnson, Computers and Intractability, San Francisco, W. H. Freeman and C., 1979. | MR 519066 | Zbl 0411.68039

8. R. M. Karp, Reducibility among Combinatorial Problems, in Complexity of Conputer Computations, R. E. MILLER and J. W. THATCHER, Eds., New York, Plenum Press, 1972, pp. 85-104. | MR 378476 | Zbl 0366.68041

9. R. M. Karp, On the Computational Complexity of Combinatorial Problems, Networks, Vol. 5, 1974, pp. 45-68. | Zbl 0324.05003

10. R. M. Karp, The Probabilistic Analysis of some Combinatorial Search Algorithm, Memorandum No. ERL-M581, University of California, Berkeley, 1976. | MR 445898

11. V. F. Kolchin, B. A. Sevastiyanov and V. P. Chistianov, Random Allocations, NewYork, John Wiley, 1978. | Zbl 0376.60003

12. H. L. Lewis, Satisfiability Problems for Propositional Calculi, Math. System Theory, Vol. 13, 1979, pp. 45-53. | MR 548548 | Zbl 0428.03035

13. R. Otter, The Multiplicative Process, Ann. Math. Statist., Vol. 20, 1949, pp. 206-224. | MR 30716 | Zbl 0033.38301

14. T. J. Shaeffer, The Complexity of Statisfiability Problems, X Sym. on Theory of Computing, 1978, pp. 216-226.

15. D. L. Snyder Random Point Processes, New York, John Wiley, 1975. | MR 501325 | Zbl 0385.60052