It is well known that the optimal solution for searching in a finite total
order set is binary search. In binary search we divide the set into two "ha
lves" by querying the middle element and continue the search on the suitabl
e half. What is the equivalent of binary search when the set P is partially
ordered? A query in this case is to a point x is an element of P, with two
possible answers: "yes" indicates that the required element is "below" x o
r "no" if the element is not below x. We show that the problem of computing
an optimal strategy for search in posets that are tree-like (or forests) i
s polynomial in the size of the tree and requires at most O(n(4) log(3) n)
steps.
Optimal solutions of such search problems are often needed in program testi
ng and debugging, where a given program is represented as a tree and a bug
should be found using a minimal set of queries. This type of search is also
applicable in searching classified large tree-like databases (e.g., the In
ternet).