[an error occurred while processing this directive]

Publications & Technical Reports

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

Lars Otten and Rina Dechter

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.