Title: The Complexity of ODDnA

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

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:

ODDnA = {(x1,...,xn) : #nA(x1,...,xn) is odd}
and, for m ≥ 2,
MODmnA = {(x1,...,xn) : #nA (x1,...,xn) ≠ 0 (mod m)},
where #nA(x1,...,xn) = A(x1) + ... + A(xn). (We identify A(x) with χA(x), where χ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 ODDnA and MODmnA:

The lower bounds above hold for nonrecursive r.e. sets A as well. (Interestingly, the lower bounds for r.e. sets follow by a general result from the lower bounds for semirecursive sets.)

In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n-1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnA 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(n,A) = {S : S can be decided with n sequential queries to A,

Q||(n,A) = {S : S can be decided with n parallel queries to A}.

We show that if A is semirecursive or r.e., but is not recursive, then these classes form non-collapsing hierarchies: The same is true if A is a jump.

Download Full Paper