Nondeterministically Evasive Functions

With an understanding of decision tree complexity we can now prove a
lower bound on a class of evasive functions. In analogy to evasive
functions whose deterministic decision tree complexity is *N* we call
functions with nondeterministic decision tree complexity *N*
*Nondeterministically evasive*. Every nondeterministically evasive
functions is evasive.

This proof establishes that nondeterministically evasive functions
have inputs that are sensitive to negation on at least half of their
bits; the result then follows from Lemma 2.2.1. Not all
evasive functions are nondeterministically evasive. OR is an example
of a nondeterministically evasive function; since Beals et al. provide an
*O*() algorithm to compute the OR of *N* bits, this
lower bound is asymptotically tight.