**Authors:**
Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl, and Frank Stephan

**Abstract:**
There has been much research over the last eleven years that considers
the *number of queries* needed to compute a function as a measure
of its complexity. We are interested in the complexity of certain
*sets* in this context. We study the sets

If *A* = *K* or *A* is semirecursive, we obtain tight
bounds on the query complexity of ODD* _{n}^{A}*
and WMOD(

We investigate when extra queries add power. We show that, for
several nonrecursive sets *A*, the more queries you can ask, the
more sets you can decide; however, there are sets for which more
queries do not help at all.