Evasive Boolean function: Difference between revisions

Revision as of 05:25, 1 July 2010

Revision as of 11:11, 26 July 2011

Line 5:

The following is a Boolean function on the three variables ''x'', ''y'', ''z'':

{| style="text-align: center; border: 1px solid darkgray;"

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

|-

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

|<math>~=~</math>

|<math>~(x \and y)~</math>

|<math>~\or~</math>

|<math>~(\neg x \and z)~</math>

|-

|[[File:Venn 0001 1011.svg|50px]]

|<math>~=~</math>

|[[File:Venn 0001 0001.svg|50px]]

|<math>~\or~</math>

|[[File:Venn 0000 1010.svg|50px]]

|}

(where <math> \wedgeand</math> is the bitwise "and", <math>\veeor</math> is the bitwise "or", and <math>\urcornerneg </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.

:( &nbsp;&nbsp;&nbsp;&nbsp;<math> ( \urcornerneg x = \text{false}) ~~\impliesRightarrow~~ ((\urcornerneg x \wedgeand z) = \text{false} ). \, </math>&nbsp;&nbsp;&nbsp;&nbsp; )

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

Line 19 ⟶ 32:

Consider this simple "and" function on three variables:

{| style="text-align: center; border: 1px solid darkgray;"

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

|-

|<math>~f(x,y,z)~</math>

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

|-

|[[File:Venn 0000 0001.svg|50px]]

|

|}

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.