Evasive Boolean function: Difference between revisions

Revision as of 16:55, 19 January 2012

Revision as of 16:57, 19 January 2012

Line 41:

|}

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 in generarlgeneral 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 ==