Skip to main content
On the query complexity of sets
21st International Symposium on Mathematical Foundations of Computer Science (MFCS ’96) (1996)
  • Richard Beigel, Yale University
  • William Gasarch, University of Maryland at College Park
  • Martin Kummer, Universität Karlsruhe
  • Georgia Martin, University of Maryland at College Park
  • Timothy H. McNicholl, Ottawa University
  • Frank Stephan, Ruprecht-Karls-Universität
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.
Publication Date
Crakow, Poland
Copyright Springer-Verlag 1996. The final publication is available at Springer via

Citation Information
Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, et al.. "On the query complexity of sets" 21st International Symposium on Mathematical Foundations of Computer Science (MFCS ’96) (1996)
Available at: