Evasive Boolean function

In mathematics, an Evasive Boolean function f (on n variables) is a Boolean function for which every Decision tree Algorithm has running time of exactly n.
Meaning that 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

Let's examine the 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 2 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=false=>(\urcorner x\wedge z)=false)$
If x is false, the algorithm checks the value of z and returns it.

A simple example for an evasive boolean function

Let's examine the simple and function on 3 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).
Meaning, 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.
Note that 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 the 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'll show 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:
like 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

• Boolean function
• Boolean algebra (logic)

• Decision tree model
• Adversary (online algorithm)