go-v.orgcodex
Menu
Page tools

codex · Philosophy

Evasive Boolean function

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

Wikipedia contributors, "Evasive Boolean function", Wikipedia, revision 1337262166, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex