Evasive Boolean function: Difference between revisions

Revision as of 18:50, 30 January 2010

Revision as of 18:53, 30 January 2010

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>

Meaning that every [[Decision tree model|Decision tree Algorithm]] that represents the function has a, at worst case, a running time of n.

== Examples ==

Line 26:

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

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

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>

thisThis input (0 for all Or nodes' children, and 1 for all And nodes' children) forces the algorithm to check all nodes: <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>

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.