Evasive Boolean function: Difference between revisions

Revision as of 19:01, 30 January 2010

Revision as of 03:22, 31 January 2010

Line 1:

In [[mathematics]], an '''Evasiveevasive Boolean function''' f''&fnof;'' (onof ''n'' variables) is a [[Boolean function]] for which every [[Decision tree model|Decisiondecision tree Algorithmalgorithm]] has running time of exactly &nbsp;''n''. <br> Consequently every [[Decision tree model|decision tree algorithm]] that represents the function has, at worst case, a running time of&nbsp;''n''.

Meaning that every [[Decision tree model|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'sThe examinefollowing theis booleana Boolean function on the three varibles ''x'',&nbsp;''y'',&nbsp;''z'': <br>

<math>f(x,y,z) = (x \wedge y) \vee (\urcorner x \wedge z)</math> <br>

: <math>f(x,y,z) = (x \wedge y) \vee (\urcorner x \wedge z) \, </math>

(where <math> \wedge</math> is the bitwise "and", <math>\vee</math> is the bitwise "or", <math>\urcorner </math> is the bitwise "not").) <br>

This function is not evasive, because there is a decision tree that solves it by checking exactly 2 variables: <br>

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 &nbsp;''x''. If ''x'' is true, the algorithm checks the value of ''y'' and returns it. <br>

: <math> ( \urcorner x = \text{false} =>\implies (\urcorner x \wedge z) = \text{false} ). \, </math> <br>

If x is false, the algorithm checks the value of z and returns it. <br>

If ''x'' is false, the algorithm checks the value of ''z'' and returns it. <br>

=== A simple example for an evasive boolean function ===

Let'sConsider examine thethis simple "and" function on 3three variables: <br>

<math>f(x,y,z) = (x \wedge y \wedge z)</math> <br>

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). <br>

: <math>f(x,y,z) = (x \wedge y) \vee (\urcorner x \wedge z)</math> <br>

Meaning, the functions: And, Or (on n variables) are evasive.

A worst -case input (for every algorithm) is &nbsp;1,&nbsp;1,&nbsp;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). <br> Hence the functions: "and", "or" (on ''n'' variables) are evasive.

== Binary zero-sum games ==

For the case of binary [[Zerozero-sum game]] gamess, every [[evaluation function]] is evasive. <br>

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). <br>

In the Binary case, the max function equals the bitwise or, and the min function equals the bitwise and. <br>

A decision tree for this game will be of the form: <br>

* every leaf will have value in {0,1}.

* every node is connected to one of {and, or}

<br>

Note that inIn 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). <br>

For every such tree with <math>n</math> leaves, the running time in the worst case is <math>n</math> (meaning that the algorithm must check all the leaves): <br>

We'll show an [[Adversary (online algorithm)|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. <br>

In the Binarybinary case, the max function equals the bitwise &nbsp;"or", and the min function equals the bitwise &nbsp;"and". <br>

This input (0 for all Or nodes' children, and 1 for all And nodes' children) forces the algorithm to check all nodes: <br>

like in the second example

A decision tree for this game will be of thethis form: <br>

* every leaf will have value in {0,&nbsp;1}.

* every node is connected to one of {"and", &nbsp;"or"}

For every such tree with <math>''n</math>'' leaves, the running time in the worst case is <math>''n</math>'' (meaning that the algorithm must check all the leaves): <br>

We'll showwill exhibit an [[Adversary (online algorithm)|adversary]] that produces a worst -case input -&ndash; 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. <br>

This input (0 for all Or nodes' children, and 1 for all And nodes' children) forces the algorithm to check all nodes: <br>

likeAs 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==