Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem |
| |
Authors: | John Franco Marvin Paull |
| |
Institution: | Case Western Reserve University, Case Institute of Technology, Crawford Hall, Cleveland, OH 44106, USA;Rutgers University, New Brunswick, NJ 08903, USA |
| |
Abstract: | We look at the instance distributions used by Goldberg 3] for showing that the Davis Putnam Procedure has polynomial average complexity and show that, in a sense, all these distributions are unreasonable. We then present a ‘reasonable’ family of instance distributions F and show that for each distribution in F a variant of the Davis Putnam Procedure without the pure literal rule requires exponential time with probability 1. In addition, we show that adding subsumption still results in exponential complexity with probability 1. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|