Recently a randomized algorithm based on Davis and Putnam Procedure was designed in [16] for the purpose of solving the satisfiability problem. In this letter another mOnte Carlo algorithm followign from an original algorithm [4] is proposed. The average performance of the algorithm is polynomial and the probability that the algorithm fails to yield a correct answer for some data is less than #epsilon#. Results are compared with those given in [16] and show an interesting performance for our algorithm.
展开▼