Accession Number : ADA185544

Title :   Probabilistic Performance of a Heuristic for the Satisfiability Problem.

Descriptive Note : Technical rept. 30 Sep 84-May 86,

Corporate Author : INDIANA UNIV AT BLOOMINGTON DEPT OF COMPUTER SCIENCE

Personal Author(s) : Franco, John ; Ho, Yuan C

PDF Url : ADA185544

Report Date : May 1986

Pagination or Media Count : 22

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.

Descriptors :   *PROBABILITY DISTRIBUTION FUNCTIONS, ALGORITHMS, BEHAVIOR, BOOLEAN ALGEBRA, HEURISTIC METHODS, POLYNOMIALS, PROBABILITY, TIME, VARIABLES, POLYNOMIALS

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE