Probabilistic analysis and performance measurement of algorithms for the satisfiability problem (np-complete, distribution, transformation)
Ming-Te Chao · 1985
This thesis studies the probabilistic behavior of some algorithms for solving SATISFIABILITY by both analysis and experiment. Underlying the study is a parameterized probabilistic distribution for SATISFIABILITY in which every clause in an instance contains a constant number of literals. By adjusting the parameter, the model can generate instances from those which are satisfiable with high probability to those which are unsatisfiable with high probability. The algorithms use the strategies of partitioning and reduction based on unit clauses. They also use literal selection heuristics in extending partial truth assignments. All the algorithms are shown to perform well over a range of parameter of the probabilistic model.