There has been much research over the last eleven years that considers the number of queriesneeded 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 ODDnA={(x1,..., xn)∶¦A ∩ {x1,..., xn}¦ is odd} and WMOD(m)nA={(x1,..., xn)∶¦A ∩ {x1,..., xn}¦≢0 (mod m)}.

If A=K or A is semirecursive, we obtain tight bounds on the query complexity of ODDnA and WMOD(m)nA. We obtain lower bounds for A r.e. The lower bounds for A r.e. are derived fromthe lower bounds for A semirecursive. We obtain that every tt-degree has a set A such that ODDnA requires n parallel queries to A, and a set B such that ODDnB can be decided with one query to B. Hence for bounded-query complexity, how information is packaged is more important than Turing degree.

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.