In this chapter we consider increasingly general classes of functions. We first examine lower bounds for tree functions in Section 4.1 and prove () oracle queries are required to compute a tree function of N bits.
We define nondeterministic decision tree complexity in Section 4.2. We then prove that () oracle queries are required to compute any N bit Boolean function with nondeterministic decision tree complexity N in Section 4.3. Finally in Section 4.4 we present our most general result: () oracle queries are required to compute a class of Boolean functions that meet a sensitivity condition and have deterministic decision tree complexity D(f ).