Title:
The Complexity of ODD_{n}^{A}
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:
ODD_{n}^{A} = {(x_{1},...,x_{n}) :
#_{n}^{A}(x_{1},...,x_{n}) is odd}
and, for m ≥ 2,
MODm_{n}^{A} = {(x_{1},...,x_{n}) : #_{n}^{A} (x_{1},...,x_{n})
≠ 0 (mod m)},
where
#_{n}^{A}(x_{1},...,x_{n})
= A(x_{1}) + ... + A(x_{n}). (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 ODD_{n}^{A} and
MODm_{n}^{A}:

ODD_{n}^{A} can be decided with n
parallel queries to A, but not with n1.

ODD_{n}^{A} can be decided with ceiling(log(n+1))
sequential queries to A but not with ceiling(log(n+1))1.

MODm_{n}^{A} can be decided with ceiling(n/m)+floor(n/m)
parallel
queries to A but not with ceiling(n/m)+floor(n/m)1.

MODm_{n}^{A} can be decided with ceiling(log(ceiling(n/m)+floor(n/m)+1)) sequential queries to A but not with
ceiling(log(ceiling(n/m)+floor(n/m)+1))1.
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 truthtable degree contains a set
A such that ODD_{n}^{A} cannot be
decided with n1 parallel queries to A. Since every
truthtable degree also contains a set B such that
ODD_{n}^{A} 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 noncollapsing hierarchies:

Q(0,A) ⊂ Q(1,A) ⊂ Q(1,A) ⊂ ...

Q_{}(0,A) ⊂ Q_{}(1,A) ⊂ Q_{}(1,A) ⊂ ...
The same is true if A is a jump.
Download Full Paper