Abstract

For a fixed set A, the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: $ODD^A_n = \{: {\tt\#}^A_n \text{is odd}\}$ and, for $m \geq 2,$ $\text{MOD}m^A_n = \{:{\tt\#}^A_n \not\equiv 0 \},$ where ${\tt\#}^A_n = A+\cdots+A$. with $\chi_A $, where $\chi_A$ is the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide $\text{ODD}^A_n$ and $\text{MOD}m^A_n: \bullet\text{ODD}^A_n$ can be decided with n parallel queries to A, but not with n - 1. $\bullet \text{ODD}^A_n$ can be decided with $\lceil log\rceil$ sequential queries to A but not with $\lceil log\rceil - 1. \bullet\text{MOD}m^A_n$ can be decided with $\lceil n/m\rceil + \lfloor n/m\rfloor$ parallel queries to A but not with $\lceil n/m\rceil + \lfloor n/m\rfloor - 1. \bullet\text{MOD}m^A_n$ can be decided with $\lceil log\rceil$ sequential queries to A but not with $\lceil log\rceil - 1$. The lower bounds above hold for nonrecursive recursively enumerable sets A as well. In particular, every nonzero truth-table degree contains a set A such that $\text{ODD}^A_n$ cannot be decided with n - 1 parallel queries to A. Since every truth-table degree also contains a set B such that $\text{ODD}^B_n$ can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, $Q = \{S : S \text{can be decided with n sequential queries to} A\},\\Q_\parallel = \{S : S \text{can be decided with n parallel queries to} A\}.$ We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: $\bullet Q \subset Q \subset Q \subset\cdots\\ \bullet Q_\parallel \subset Q_\parallel \subset Q_\parallel \subset\cdots$ The same is true if A is a jump.