Boolean Functions

In this chapter we consider increasingly general classes of functions. We first examine lower bounds for tree functions in Section 4.1 and prove $\Omega$($\sqrt[4]{{N}}$) 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 $\Omega$($\sqrt{{N}}$) 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: $\Omega$($\sqrt[4]{{D(f)}}$) oracle queries are required to compute a class of Boolean functions that meet a sensitivity condition and have deterministic decision tree complexity D(f ).