Approximate Resolution of Hard Numbering Problems

Abstract

We present a new method for estimating the number of solutions of constraint satisfaction problems 1 . We use a stochastic forward checking algorithm for drawing a sample of paths from a search tree. With this sample, we compute two values related to the number of solutions of a CSP instance. First, an unbiased estimate, second, a lower bound with an arbitrary low error probability. We will describe applications to the Boolean Satisfiability problem and the Queens problem. We shall give some experimental results for these problems. Introduction The class NP is the set of decision problems whose instances are assertions that can be proved in polynomial time. The NP-Complete problems are the hardest problems in NP. These can not be solved in polynomial time under the assumption P 6= NP . All these problems have the same expression power in the sense that every NP-Complete problem can be polynomialy reduced to each another (Garey & Johnson 1979). Some of them, such as CSP 2...