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:

$~f(x,y,z)~$	$~=~$	$~(x\land y)~$	$~\lor ~$	$~(\neg x\land z)~$
	$~=~$		$~\lor ~$

(where $\land$ is the bitwise "and", $\lor$ 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\land 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 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.

See also

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