Evasive Boolean function: Difference between revisions

Revision as of 08:17, 3 February 2024

Latest revision as of 08:32, 25 February 2024

(3 intermediate revisions by one other user not shown)

Line 2:

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

Line 31:

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

==References==

Line 37 ⟶ 45:

[[Category:Boolean algebra]]

[[Category:Decision trees]]