Evasive Boolean function


In mathematics, an evasive Boolean function ƒ 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 variables x, y, z:
.
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.
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:
A worst-case input is 1, 1, 1. In every order we choose to check the variables, we have to check all of them. Hence the functions: "and", "or" 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.
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:
For every such tree with n leaves, the running time in the worst case is n :
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 forces the algorithm to check all nodes:
As in the second example