Counting by Statistics on Search Trees: Application to Constraint Satisfaction Problems

Article type: Research Article

Authors: Bailleux, Olivier^{a; *} | Chabrier, Jean-Jacques^{b; 1}

Affiliations: [a] C.R.I.L, Université d'Artois, IUT de Lens, Rue de l'Université, SP16, F62300 LENS, CEDEX, France | [b] C.R.I.D, Université de Bourgogne, Faculté des Sciences Mirande, BP 400, F21011 DIJON CEDEX, France

Correspondence: [*] Corresponding author. E-mail: bailleux@cril.univ-artois.fr.

Note: [1] E-mail: chabrier@crid.u-bourgogne.fr.

Abstract: In 1975, Knuth proposed a simple statistical method for investigating search trees. We use this technique for estimating the number of solutions of constraint satisfaction problem (CSP) and boolean satisfiability problem (SAT) instances. We show that, depending on domain reductions, tree-based estimates have a lower variance than estimates based on uniform sampling from the search space. Nevertheless, because the variance remains extremely high in the general case, a confidence interval cannot be derived, but a lower bound of the number of solutions. These results are confirmed by many experiments.

Keywords: Statistical counting, #P-complete problems, Constraint satisfaction, Satisfiability

DOI: 10.3233/IDA-1997-1404

Journal: Intelligent Data Analysis, vol. 1, no. 4, pp. 263-274, 1997