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 variables x, y, z:

[math]\displaystyle{ ~f(x,y,z)~ }[/math]	[math]\displaystyle{ ~=~ }[/math]	[math]\displaystyle{ ~(x \land y)~ }[/math]	[math]\displaystyle{ ~\lor~ }[/math]	[math]\displaystyle{ ~(\neg x \land z)~ }[/math]
	[math]\displaystyle{ ~=~ }[/math]		[math]\displaystyle{ ~\lor~ }[/math]

(where [math]\displaystyle{ \land }[/math] is the bitwise "and", [math]\displaystyle{ \lor }[/math] is the bitwise "or", and [math]\displaystyle{ \neg }[/math] 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.

(     [math]\displaystyle{ (\neg x = \text{false}) ~~\Rightarrow~~ ((\neg x \land z) = \text{false}) }[/math]     )

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:

[math]\displaystyle{ ~f(x,y,z)~ }[/math]	[math]\displaystyle{ ~= (x \wedge y \wedge z)~ }[/math]

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 in general 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.