A probabilistic analysis of a new satisfiability algorithm
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1982)
- Volume: 16, Issue: 3, page 201-223
- ISSN: 0988-3754
Access Full Article
top
How to cite
topApolloni, B., and Di Gregorio, S.. "A probabilistic analysis of a new satisfiability algorithm." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 16.3 (1982): 201-223. <http://eudml.org/doc/92162>.
@article{Apolloni1982,
author = {Apolloni, B., Di Gregorio, S.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {average polynomial time cost; full randomness in the logical variables; average running time; Galil tree method; conjunctive normal forms; complexity of NP-complete problems},
language = {eng},
number = {3},
pages = {201-223},
publisher = {EDP-Sciences},
title = {A probabilistic analysis of a new satisfiability algorithm},
url = {http://eudml.org/doc/92162},
volume = {16},
year = {1982},
}
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
PB - EDP-Sciences
VL - 16
IS - 3
SP - 201
EP - 223
LA - eng
KW - average polynomial time cost; full randomness in the logical variables; average running time; Galil tree method; conjunctive normal forms; complexity of NP-complete problems
UR - http://eudml.org/doc/92162
ER -
References
top- 1. K. J. ASTROM, Introduction to Stochastic Control Theory, NewYork, London, Academic Press, 1970. Zbl0226.93027MR270799
- 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. Zbl0095.32803MR112177
- 4. S. A. COOK, The Complexity of Theorem-Proving Procedures, Proc. third A.C.M. Symposium on Theory of Computing, 1971, pp. 151-158. Zbl0253.68020
- 5. H. KRAMER, Mathematical Methods of Statistics, Princeton, Princeton University Press, 1945. Zbl0063.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. Zbl0358.68132
- 7. M. R. GAREY and D. S. JOHNSON, Computers and Intractability, San Francisco, W. H. Freeman and C., 1979. Zbl0411.68039MR519066
- 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. Zbl0366.68041MR378476
- 9. R. M. KARP, On the Computational Complexity of Combinatorial Problems, Networks, Vol. 5, 1974, pp. 45-68. Zbl0324.05003
- 10. R. M. KARP, The Probabilistic Analysis of some Combinatorial Search Algorithm, Memorandum No. ERL-M581, University of California, Berkeley, 1976. Zbl0368.68035MR445898
- 11. V. F. KOLCHIN, B. A. SEVASTIYANOV and V. P. CHISTIANOV, Random Allocations, NewYork, John Wiley, 1978. Zbl0376.60003
- 12. H. L. LEWIS, Satisfiability Problems for Propositional Calculi, Math. System Theory, Vol. 13, 1979, pp. 45-53. Zbl0428.03035MR548548
- 13. R. OTTER, The Multiplicative Process, Ann. Math. Statist., Vol. 20, 1949, pp. 206-224. Zbl0033.38301MR30716
- 14. T. J. SHAEFFER, The Complexity of Statisfiability Problems, X Sym. on Theory of Computing, 1978, pp. 216-226.
- 15. D. L. SNYDERRandom Point Processes, New York, John Wiley, 1975. Zbl0385.60052MR501325
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.