R160a | |
Refined Bounds for Instance-Based Search Complexity
of Counting and Other #P Problems
Lars Otten and Rina Dechter |
Abstract
This paper presents measures for upper and lower bounding the instance-
based complexity of AND/OR search algorithms for solution counting and related
#P problems. This can be of utmost importance in selecting the right set of pa-
rameters for fitting an algorithm to a problem instance and in devising heuristics
during execution. To this end we estimate the size of the search space, with spe-
cial consideration given to the impact of determinism in a problem. The resulting
schemes are evaluated empirically on a variety of problem instances; in many
cases relatively tight bounds are obtained, far better than those implied by the
tree width or hypertree width. Specific results are provided detailing how these
measures can be useful for discriminating between variable orderings.
[pdf] |