Evasive Boolean function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.


An example for a non-evasive boolean function[edit]

The following is a Boolean function on the three variables xyz:

~f(x,y,z)~ ~=~ ~(x \and y)~ ~\or~ ~(\neg x \and z)~
Venn 0001 1011.svg ~=~ Venn 0001 0001.svg ~\or~ Venn 0000 1010.svg

(where \and is the bitwise "and", \or is the bitwise "or", and \neg 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.

(     (\neg x = \text{false}) ~~\Rightarrow~~ ((\neg x \and 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[edit]

Consider this simple "and" function on three variables:

~f(x,y,z)~ ~= (x \wedge y \wedge z)~
Venn 0000 0001.svg

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[edit]

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[edit]