Evasive Boolean function

In mathematics, an evasive Boolean function ƒ (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.

Examples

An example for a non-evasive boolean function

The following is a Boolean function on the three varibles x, y, z:

$f(x,y,z)=(x\wedge y)\vee (\urcorner x\wedge z)\,$

(where $\wedge$ is the bitwise "and", $\vee$ is the bitwise "or", $\urcorner$ is the bitwise "not").

This function is not evasive, because there is a decision tree that solves it by checking exactly two variables: The algorithm first checks the value of x. If x is true, the algorithm checks the value of y and returns it.

$(\urcorner x={\text{false}}\implies (\urcorner x\wedge z)={\text{false}}).\,$

If x is false, the algorithm checks the value of z and returns it.

A simple example for an evasive boolean function

Consider this simple "and" function on three variables:

$f(x,y,z)=(x\wedge y\wedge z)$

A worst-case input (for every algorithm) is 1, 1, 1. In every order we choose to check the variables, we have to check all of them. (note that there could be a different worst-case input for every decision tree algorithm). Hence the functions: "and", "or" (on n variables) are evasive.

Binary zero-sum games

For the case of binary zero-sum games, every evaluation function is evasive.

In every zero-sum game, the value of the game is achieved by the minimax algorithm (player 1 tries to maximize the profit, and player 2 tries to minimize the cost).

In the binary case, the max function equals the bitwise "or", and the min function equals the bitwise "and".

A decision tree for this game will be of this form:

• every leaf will have value in {0, 1}.
• every node is connected to one of {"and", "or"}

For every such tree with n leaves, the running time in the worst case is n (meaning that the algorithm must check all the leaves):

We will exhibit an adversary that produces a worst-case input – for every leaf that the algorithm checks, the adversary will answer 0 if the leaf's parent is an Or node, and 1 if the parent is an And node.

This input (0 for all Or nodes' children, and 1 for all And nodes' children) forces the algorithm to check all nodes:

As in the second example

• in order to calculate the Or result, if all children are 0 we must check them all.
• In order to calculate the and result, if all children are 1 we must check them all.

See also

• Aanderaa–Karp–Rosenberg conjecture, the conjecture that every nontrivial monotone graph property is evasive.