List of Abbreviations

A x B:

The Cartesian product of the sets A and B.

AND:

The Boolean function that returns 1 if and only if every input bit is 1.

D(f ):

The decision tree complexity of the function f.

D(f, x):

The minimum number of bits of input x that determine the value of f (x).

D₀(f ):

The nondeterministic decision tree complexity of verifying that f (x) = 0.

D₁(f ):

The nondeterministic decision tree complexity of verifying that f (x) = 1.

N(f ):

The nondeterministic decision tree complexity of the function f.

OR:

The Boolean function that returns 0 if and only if every input bit is 0.

PARITY:

The Boolean function that returns 1 if and only if the number of 1 bits in the input is even.

MAJORITY:

The Boolean function that returns 1 if and only if more than half of the input bits are 1.