Probabilistic Analysis of Algorithms for NP-Complete Problems.
Annual rept. Oct 85-Sep 86,
INDIANA UNIV AT BLOOMINGTON DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The probabilistic performance of a number of algorithms for the NP-complete satisfiability Problem SAT has been investigated analytically and experimentally using a fixed-clause-length model generating n clauses of k - 3 literals taken from r variables as well as a random-clause-length model generating n clauses containing each of r variables independently with probability P. In the case of the random instance I of SAT with probability approachingas in and r get large when a solution exists for I. In the case of the fixed-clause-length model, we have discovered an algorithm which almost always finds a solution to random satisfiable instances of SAT with k 3. We have also shown that none of a wide class of algorithms can verify unsatisfiability in polynomial time almost always.