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:
-
ODDnA can be decided with n
parallel queries to A, but not with n-1.
-
ODDnA can be decided with ceiling(log(n+1))
sequential queries to A but not with ceiling(log(n+1))-1.
-
MODmnA can be decided with ceiling(n/m)+floor(n/m)
parallel
queries to A but not with ceiling(n/m)+floor(n/m)-1.
-
MODmnA 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 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:
-
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