Evasive Boolean function: Difference between revisions

Revision as of 18:53, 30 January 2010

Revision as of 19:01, 30 January 2010

Line 8:

(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>

The algorithm first checkchecks the value of x. If x is true, the algorithm checks the value of y, and returns it. <br>

<math> ( \urcorner x = false => (\urcorner x \wedge z) = false )</math> <br>

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

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

Line 21:

For the case of binary [[Zero-sum]] games, every [[evaluation function]] is evasive. <br>

Note that in every zero-sum game, the value of the game is achivedachieved 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>

Line 28:

<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 produceproduces a worst case input - for every leaf that the algorithm checkchecks, the adversary will answer 0 if the leaf's parent is an Or node, and 1 if the parent is aban 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>

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

{{Col-begin}}

{{Col-break|width=30%}}

* [[Boolean function]]

* [[Boolean algebra (logic)]]

{{Col-break}}

* [[Decision tree model]]

* [[Adversary (online algorithm)]]

{{Col-end}}

[[Category:Boolean algebra]]