Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR96-044 | 20th March 1997 00:00

#### Optimal Search in Trees Revision of: TR96-044

Revision #1
Authors: Yosi Ben-Asher, Eitan Farchi, Ilan Newman
Accepted on: 20th March 1997 00:00
Keywords:

Abstract:

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 halves'' by querying the middle
element and continue the search on the suitable 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\in P$, with
two possible answers: 'yes', indicates that the required element
is below'' $x$, or 'no' if the element is not bellow $x$.
We show that the problem of computing an optimal strategy
for search in Posets that are tree-like (or forests) is
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 testing 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 data bases (e.g. the Internet).

### Paper:

TR96-044 | 6th August 1996 00:00

#### Optimal Search in Trees

TR96-044
Authors: Yosi Ben-Asher, Ilan Newman
Publication: 26th August 1996 12:05
Keywords:

Abstract:

It is well known that the optimal solution for
searching in
a finite total order set is the binary search.
In the binary search we
divide the set into two halves'', by querying the middle
element, and continue the search on the suitable 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\in P$, with
two possible answers: 'yes', indicates that the required element
is below'' $x$, or 'no' if the element is not bellow $x$.
We show that the problem of computing an optimal strategy
for search in Posets that are tree-like (or forests) is
polynomial in the size of
the tree, and requires at most $O(n^2\log^2 n)$ steps.

Optimal solutions of such search problems are often
needed in program testing and debugging,
where a given program is represented as a tree
and a bug should be found using a minimal set of queries.

ISSN 1433-8092 | Imprint