A probabilistic analysis of a new satisfiability algorithm
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) no. 3, pp. 201-223.
@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},
     pages = {201--223},
     publisher = {EDP-Sciences},
     volume = {16},
     number = {3},
     year = {1982},
     zbl = {0489.68038},
     mrnumber = {686913},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1982__16_3_201_0/}
}
TY  - JOUR
AU  - Apolloni, B.
AU  - Di Gregorio, S.
TI  - A probabilistic analysis of a new satisfiability algorithm
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1982
DA  - 1982///
SP  - 201
EP  - 223
VL  - 16
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1982__16_3_201_0/
UR  - https://zbmath.org/?q=an%3A0489.68038
UR  - https://www.ams.org/mathscinet-getitem?mr=686913
LA  - en
ID  - ITA_1982__16_3_201_0
ER  - 
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) no. 3, pp. 201-223. http://www.numdam.org/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