Evasive Boolean function: Difference between revisions

Revision as of 08:01, 24 November 2014

Revision as of 08:21, 24 November 2014

Line 1:

{{unreferenced|date=November 2014}}

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