Equilibrium points of an AND–OR tree: Under constraints on probability

We consider a depth-first search based algorithm to find the truth value of the root of an AND–OR tree. The cost is measured by the number of leaves probed during the computation. We consider probability distributions on the truth assignments, and restrict the attention to distributions that have the following properties: 1. The inputs come from a product distribution. 2. The output probability (of the root being assigned zero) is some fixed r   such that 0