Probabilistic Analysis of Algorithms for NP-Complete Problems.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1986
- Accession Number
- ADA179537
Entities
People
- John Franco
Organizations
- Indiana University Bloomington