Probabilistic analysis of the pure literal heuristic for the satisfiability problem |
| |
Authors: | John Franco |
| |
Affiliation: | (1) Department of Computer Science, Indiana University, 47405 Bloomington, IN, USA |
| |
Abstract: | An algorithm for the SATISFIABILITY problem is presented and a probabilistic analysis is performed. The analysis is based on an instance distribution which is parametrized to simulate a variety of sample characteristics. The algorithm either correctly determines whether a given instance of SATISFIABILITY has a solution or gives up. It is shown that the algorithm runs in polynomial time and gives up with probability approaching zero as input size approaches infinity for a range of parameter values. This result is an improvement over the results in [3] and [4]. |
| |
Keywords: | Average complexity satisfiability pure literal heuristic Davis-Putnam procedure |
本文献已被 SpringerLink 等数据库收录! |