Evasive Boolean function: Difference between revisions

Revision as of 03:22, 31 January 2010

Latest revision as of 08:32, 25 February 2024

(19 intermediate revisions by 12 users not shown)

Line 1:

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

==Definition==

The type of algorithms considered in the definition of evasive Boolean function are [[decision tree]]s in which each internal node tests the value of one of the given Boolean variables, and branches accordingly. Each leaf node of the tree specifies the value of the function for inputs that reach that node. The worst case [[decision tree complexity]] of a given decision tree is the number of variables examined on the longest root-to-leaf path of the tree. Every <math>n</math>-variable function has a decision tree algorithm that examines exactly <math>n</math> variables on all inputs, using a decision tree in which all nodes at level <math>i</math> test the <math>i</math>th variable. A function is evasive if no other decision tree for the same function has smaller complexity. For an evasive function, any decision tree must have at least one input that leads to a path in the tree along which all input variables are examined.<ref name=rv/>

== Examples ==

It is trivial to construct non-evasive functions by constructing decision trees on which every branch terminates before testing all variables. For instance, the always-true function has a decision tree with no tests. For a less trivial example, in which all variables are used to determine the function value, consider the function of three variables <math>x</math>, <math>y</math>, and <math>z</math> that returns either <math>y</math> or <math>z</math> according to whether <math>x</math> is true or false respectively. It has a decision tree that first tests <math>x</math>, and then tests only one of <math>y</math> or <math>z</math> on each branch.

=== An example for a non-evasive boolean function ===

The following is a Boolean function on the three varibles ''x'',&nbsp;''y'',&nbsp;''z'':

: <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").

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.

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

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:

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

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). Hence the functions: "and", "or" (on ''n'' variables) are evasive.

== Binary zero-sum games ==

For the case of binary [[zero-sum game]]s, every [[evaluation function]] is evasive.

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

In the binary case, the max function equals the bitwise&nbsp;"or", and the min function equals the bitwise&nbsp;"and".

A decision tree for this game will be of this form:

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

* every node is connected to one of {"and",&nbsp;"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):

If a branch of a decision tree terminates before testing all variables, then it gives the function value for an even number of combinations of arguments: <math>2^{n-t}</math> combinations, where <math>n</math> is the number of variables and <math>t</math> is the number tested along that branch. Therefore, if a Boolean function has an odd number of combinations of arguments for which it is true, then it must be evasive.<ref name=rv/> For instance, the [[logical and]] and [[logical or]] functions are true for 1 and <math>2^n-1</math> combinations of arguments, respectively, both of which are odd numbers (for <math>n > 0</math>), so they are evasive.

We will 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.

==History==

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

The concept of an evasive function was introduced in connection with the study of [[graph algorithm]]s for graphs defined in an [[implicit graph]] model, where an algorithm has access to the graph only through a subroutine for testing the adjacency of vertices. In this application, a graph property can be described as a Boolean function whose input variables are true if an edge is present between two vertices, and a property is evasive if every algorithm must (on some inputs) test the existence of each potential edge. Early work in this area proved that a constant fraction of edges must be tested for any nontrivial monotone graph property; here "nontrivial" means that the function has more than one value, and "monotone" means that adding edges to a graph cannot change the function value from true to false. These partial results motivated the formulation of the [[Aanderaa–Karp–Rosenberg conjecture]], still unproven, according to which all nontrivial monotone graph properties are evasive.<ref name=rv>{{citation

| last1 = Rivest | first1 = Ronald L. | author1-link = Ronald Rivest

| last2 = Vuillemin | first2 = Jean | author2-link = Jean Vuillemin

| date = December 1976

| doi = 10.1016/0304-3975(76)90053-0

| issue = 3

| journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]

| pages = 371–384

| title = On recognizing graph properties from adjacency matrices

| volume = 3}}. This reference calls evasive properties "exhaustive", but mentions that the word "evasive" is used instead by several other earlier unpublished works.</ref>

The Aanderaa–Karp–Rosenberg conjecture would follow from a more general conjecture on the evasiveness of Boolean functions: that every nontrivial monotone Boolean function that has symmetries taking any variable to any other variable is evasive. This conjecture also remains unproven, but it is known to be true for certain values of <math>n</math>, including the [[prime power]]s.<ref name=rv/><ref>{{citation

As in the second example

| last1 = Kahn | first1 = Jeff

* in order to calculate the Or result, if all children are 0 we must check them all.

| last2 = Saks | first2 = Michael | author2-link = Michael Saks (mathematician)

* In order to calculate the and result, if all children are 1 we must check them all.

| last3 = Sturtevant | first3 = Dean

| date = December 1984

| doi = 10.1007/bf02579140

| issue = 4

| journal = [[Combinatorica]]

| pages = 297–306

| title = A topological approach to evasiveness

| volume = 4}}</ref> It has been called the '''evasiveness conjecture'''.<ref>{{citation

| last = Kulkarni | first = Raghav

| date = September 2013

| doi = 10.1145/2527748.2527763

| issue = 3

| journal = [[ACM SIGACT News]]

| pages = 42–55

| title = Gems in decision tree complexity revisited

| volume = 44}}</ref>

==See alsoReferences==

{{Col-beginreflist}}

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

* [[Boolean function]]

* [[Boolean algebra (logic)]]

{{Col-break}}

* [[Decision tree model]]

* [[Adversary (online algorithm)]]

{{Col-end}}

[[Category:Boolean algebra]]

[[Category:Decision trees]]