Probabilistic Performance of a Heuristic for the Satisfiability Problem.
Abstract
An algorithm for the Satisfiability problem is presented and its probabilistic behavior is analysed when combined with two other algorithms studied earlier. The analysis is based on an instance distribution which is parameterized to simulate a variety of sample characteristics. The algorithm dynamically assigns values to literals appearing in a given instance until a satisfying assignment is found or the algorithm gives up without determining whether or not a solution exists. It is shown that if n clauses are constructed independently from r boolean variables where the probability that a variable appears in a clause as a positive literal is p and as a negative literal is p then almost all randomly generated instances of satisfiability are solved in polynomial time under certain conditions. Thus the combined algorithm is very effective in the probabilistic sense on instances of SAT that have solutions.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1986
- Accession Number
- ADA185544
Entities
People
- John Franco
- Yuan C. Ho
Organizations
- Indiana University Bloomington