|

R160
Refined Bounds for Instance-Based Search Complexity of Counting and Other #P Problems

Lars Otten and Rina Dechter

Abstract
We present measures for bounding the instance-based complexity of AND/OR search algorithms for solution counting and related #P problems. To this end we estimate the size of the search space, with special consideration given to the impact of determinism in a problem. The resulting schemes are evaluated empirically on a variety of problem instances and shown to be quite powerful.

[pdf]