6533b7cffe1ef96bd1258ef6
RESEARCH PRODUCT
Counting by Statistics on Search Trees: Application to Constraint Satisfaction Problems
Olivier BailleuxJean-jacques Chabriersubject
Complexity of constraint satisfactionBacktrackingConstraint graphArtificial IntelligenceStatisticsConstraint satisfaction dual problemHybrid algorithm (constraint satisfaction)Local consistencyComputer Vision and Pattern RecognitionConstraint satisfactionConstraint satisfaction problemMathematicsTheoretical Computer Sciencedescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1997-10-01 | Intelligent Data Analysis |