Evasive Boolean function: Difference between revisions

Revision as of 11:20, 5 May 2014

Revision as of 08:01, 24 November 2014

Line 1:

{{unreferenced}}

In [[mathematics]], an '''evasive Boolean function''' ''ƒ'' (of ''n'' variables) is a [[Boolean function]] for which every [[Decision tree model|decision tree algorithm]] has running time of exactly ''n''. Consequently every [[Decision tree model|decision tree algorithm]] that represents the function has, at worst case, a running time of ''n''.