Probabilistic Analysis of a Generalization of the Unit Clause Literal Selection Heuristic for the k-Satisfiability Problem
Original Publication Date: 1985-Jan-31
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Chao, Ming-Te: AUTHOR [+3]
Probabilistic Analysis of' a Generdization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem Ming-Te Chao
Probabilistic Analysis of' a Generdization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem
Case Weatern Reserve University Department of Computer Engineering and Science Cleveland, 08 44106
John h c o Indiaaa University
Department of Computer Science Bloomington, IN 47405
TECHNICAL REPORT NO. 165
Probabilistic Analysis of a Generalization of the Unit Clause Literal Selection Heuristic for the ksatisfiability Problem
Ming-Te Chao, Case Western Reserve University
and John h c o , Indiana University
This material is brued on work supported by the U.S. Air Force under grant number AFOSR-840372.
Two algorithm for the k-Satiefiabiity problem are prerrented and a probabii tic analysis is performed. The analysis ir, basedl on an instance distribution which is parameterised to simulate a variety of sample characteristics. The algorithms aaaign dueu to literals appearing in a given instance of k-Satisfiability, one at a time, until a solution is found or it is discovered that further assignments cannot lead to finding a solution. One algorithm tho- the next literal from a unit clause if one exists and randomly from the eet of remaining literals otherwise. The other algorithm u w a generaliaation of the Unit-Clause rule as a heuristic for selecting the next literal: at each step a literal is choeen randomly from a clause containing the least number of literals. The algorithms run in polynomial time and it ia shown that they find a solution to a random instance of k-Satisfiabiility with probability bounded from below by a constant greater than sero for two different rangea of parameter values. It is also shown that the second algorithm mentioned finds a solution with probability approaching one for a wide range of parameter values.
This paper is concerned with the probabilistic performance of henristia for the k-Satisfiability problem (k-SAT). &-SAT is the problem of determining whether all
of a collection of k-literal disjunctiom (claw) of Boolean variablea are true for some truth awignment to the variablea. Thb problem b NP-complete ao there is
no known polynomial time algorithm for solving it. &-SAT ia a rpecial cam of the Satidability problem (SAT) which b the problem of determining whether all of a collection of disjunctions of Boolean dablea am true for some truth dgnment to the variables.
The analyais is based on an equally likely instance distribution which has been used in other studiea of algorithm for thh problem. Thir model hm two paramt- tens in addition t...