Title: On the Query Complexity of Sets

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

ODDnA = {(x1,...,xn) : |A intersection {x1,...,xn}| is odd} and

WMOD(m)nA = {(x1,...,xn) : |A intersection {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 from the 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.

Download Full Paper