Nondeterministic Decision Tree Complexity

In the presentation of the most general results of this thesis we refer frequently to deterministic and nondeterministic decision tree complexity, deterministic decision trees were discussed in Section 3.1. Readers familiar with these topics can proceed directly to Section 4.3.

Let *f* be an *N*-bit Boolean function. We will use the following
definitions of László Lovász and Péter
Gács [13].

For every input *x* let *D*(*f*, *x*) denote the minimum number of bits of
*x* we could be told to convince us that *f* (*x*) takes on a particular
value. For example: *D*(OR
, 0^{N}) = *N*. If we are told fewer than
*N* bits of an input are all 0 we can not determine the value of OR
for that input. For any other input
*x* 0^{N}, *D*(OR, *x*) = 1,
because we only need to be told that one bit of the input is a 1. We
are not concerned with how many oracle queries we have to make in the
worst case to determine *f* (*x*), but rather how many bits we could be
told in the best case to be sure of the value *f* takes on *x*.