Abstract: We investigate the complexity of evaluating monotone Boolean
functions in a variant of the decision tree model. We assume that
reading different variables can incur different costs. Moreover we
employ competitive analysis as the cost measure used to evaluate the
performance of the algorithms.

This basic problem arises in severaldomains of computer science as
illustrated by the following typical examples.

Automatic diagnosis systems have been studied for a long time by the
Artificial Intelligence community. These systems employ a sequence of
tests and based on their outcomes, they provide a diagnosis (e.g.  a
patient has cancer or not, a component of a system is failing or not).
In general, it is not necessary to perform all the
available tests in order to determine the correct diagnosis.
Since different tests might incur also very different
costs, it is reasonable to look for testing procedures
that minimize the cost incurred to produce the diagnosis.


In the field of computer aided games, a central structure is
represented by the so-called game tree.
A computer builds a game tree of a certain depth in
order to precalculate the possible developments of the game
starting from the current position. It is possible to
assign a value to each leaf-state, that measures how good that
state is for the computer-player. On the basis of these values
it is then possible to  evaluate all the intermediate states and, in
particular,by knowing the child of the root with maximum value, to
decide for the most fruitful next move.
Again we find the problem of evaluating a function by only looking at a
{\em cheap} set of its variables.

Finally, query optimization is a major issue in the area of databases.
Query optimization refers to the problem of defining strategies to
evaluate queries in order to minimize the user response time. In a typical
database query, thousands of tuples are scanned to determine which of them
match the query. By carefully defining a strategy to evaluate the
attributes one can save a considerable amount of computational time. In
general, it is not necessary to evaluate all attributes of a tuple in
order to determine whether it matches the query or not and a smart choice
of the attributes to evaluate first can avoid very expensive, and, which
might be worse, redundant attribute evaluations.