Abstract
The contribution of this paper is in vieweing search for constraint processing in the context of AND/OR search spaces and in demonstrating the impact of this view on solutions counting. In a companion paper we introduce the AND/OR search space idea for probabilistic reasoning. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Familiar parameters such as the depth of a spanning tree, tree-width and path-width are shown to play a key role in characterizing the effect of AND/OR search graphs vs the traditional OR search graphs. Empirical evaluation focusing on counting demonstrates the spectrum of search and inference within the AND/OR search spaces.