Evasive Boolean function: Difference between revisions
MuffledThud (talk | contribs) m Quick-adding category Boolean algebra (using HotCat) |
No edit summary |
||
Line 1: | Line 1: | ||
In [[mathematics]], an '''Evasive Boolean function''' f (on n variables) is a [[Boolean function]] for which every [[Decision tree model|Decision tree Algorithm]] has running time of exactly n. <br> |
In [[mathematics]], an '''Evasive Boolean function''' f (on n variables) is a [[Boolean function]] for which every [[Decision tree model|Decision tree Algorithm]] has running time of exactly n. <br> |
||
Meaning that every [[Decision tree model|Decision tree Algorithm]] that represents the function has |
Meaning that every [[Decision tree model|Decision tree Algorithm]] that represents the function has, at worst case, a running time of n. |
||
== Examples == |
== Examples == |
||
Line 26: | Line 26: | ||
* every leaf will have value in {0,1}. |
* every leaf will have value in {0,1}. |
||
* every node is connected to one of {and, or} |
* every node is connected to one of {and, or} |
||
<br> |
|||
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): <br> |
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): <br> |
||
We'll show an [[Adversary (online algorithm)|adversary]] that produce a worst case input |
We'll show an [[Adversary (online algorithm)|adversary]] that produce a worst case input - for every leaf that the algorithm check, the adversary will answer 0 if the leaf's parent is an Or node, and 1 if the parent is ab And node. <br> |
||
⚫ | |||
for every leaf that the algorithm check, the adversary will answer 0 if the leaf's parent is an Or node, and 1 if the parent is ab And node. <br> |
|||
⚫ | |||
like in the second example |
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 Or result, if all children are 0 we must check them all. |
Revision as of 18:53, 30 January 2010
In mathematics, an Evasive Boolean function f (on n variables) is a Boolean function for which every Decision tree Algorithm has running time of exactly n.
Meaning that 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
Let's examine the boolean function on the three varibles x,y,z:
(where is the bitwise and, is the bitwise or, is the bitwise not.)
This function is not evasive, because there is a decision tree that solves it by checking exactly 2 variables:
The algorithm first check the value of x. If x is true, the algorithm checks the value of y, and returns it.
If x is false, the algorithm checks the value of z, and return it.
A simple example for an evasive boolean function
Let's examine the simple and function on 3 variables:
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).
Meaning, 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.
Note that in every zero-sum game, the value of the game is achived 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 the 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'll show an adversary that produce a worst case input - for every leaf that the algorithm check, the adversary will answer 0 if the leaf's parent is an Or node, and 1 if the parent is ab And node.
This input (0 for all Or nodes' children, and 1 for all And nodes' children) forces the algorithm to check all nodes:
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.