Nondeterministic Query Algorithms
Query algorithms are used to compute Boolean functions. The definition of the function is known, but input is hidden in a black box. The aim is to compute the function value using as few queries to the black box as possible. As in other computational models, different kinds of query algorithms are possible: deterministic, probabilistic, as well as non-deterministic. In this paper, the authors present a new alternative definition of non-deterministic query algorithms and study algorithm complexity in this model. They demonstrate the power of their model with an example of computing the Fano plane Boolean function.