Evasive Boolean function

In mathematics, an evasive Boolean function $f$ (of $n$ variables) is a Boolean function for which every decision tree algorithm has running time of exactly $n$. Consequently, every decision tree algorithm that represents the function has, at worst case, a running time of $n$.

Definition

The type of algorithms considered in the definition of evasive Boolean function are decision trees in which each internal node tests the value of one of the given Boolean variables, and branches accordingly. Each leaf node of the tree specifies the value of the function for inputs that reach that node. The worst case decision tree complexity of a given decision tree is the number of variables examined on the longest root-to-leaf path of the tree. Every $n$-variable function has a decision tree algorithm that examines exactly $n$ variables on all inputs, using a decision tree in which all nodes at level $i$ test the $i$th variable. A function is evasive if no other decision tree for the same function has smaller complexity. For an evasive function, any decision tree must have at least one input that leads to a path in the tree along which all input variables are examined.

Examples

It is trivial to construct non-evasive functions by constructing decision trees on which every branch terminates before testing all variables. For instance, the always-true function has a decision tree with no tests. For a less trivial example, in which all variables are used to determine the function value, consider the function of three variables $x$, $y$, and $z$ that returns either $y$ or $z$ according to whether $x$ is true or false respectively. It has a decision tree that first tests $x$, and then tests only one of $y$ or $z$ on each branch.

If a branch of a decision tree terminates before testing all variables, then it gives the function value for an even number of combinations of arguments: $2^{n-t}$ combinations, where $n$ is the number of variables and $t$ is the number tested along that branch. Therefore, if a Boolean function has an odd number of combinations of arguments for which it is true, then it must be evasive. For instance, the logical and and logical or functions are true for 1 and $2^{n}-1$ combinations of arguments, respectively, both of which are odd numbers (for $n>0$), so they are evasive.

History

The concept of an evasive function was introduced in connection with the study of graph algorithms for graphs defined in an implicit graph model, where an algorithm has access to the graph only through a subroutine for testing the adjacency of vertices. In this application, a graph property can be described as a Boolean function whose input variables are true if an edge is present between two vertices, and a property is evasive if every algorithm must (on some inputs) test the existence of each potential edge. Early work in this area proved that a constant fraction of edges must be tested for any nontrivial monotone graph property; here "nontrivial" means that the function has more than one value, and "monotone" means that adding edges to a graph cannot change the function value from true to false. These partial results motivated the formulation of the Aanderaa–Karp–Rosenberg conjecture, still unproven, according to which all nontrivial monotone graph properties are evasive.

The Aanderaa–Karp–Rosenberg conjecture would follow from a more general conjecture on the evasiveness of Boolean functions: that every nontrivial monotone Boolean function that has symmetries taking any variable to any other variable is evasive. This conjecture also remains unproven, but it is known to be true for certain values of $n$, including the prime powers. It has been called the evasiveness conjecture.