Skip to main content
The complexity of ODDnA
The Journal of Symbolic Logic (2000)
  • Richard Beigel, University of Illinois at Chicago
  • William Gasarch, University of Maryland
  • Martin Kummer, Technische Universität Chemnitz
  • Timothy H. McNicholl, University of Dallas
  • Frank Stephan, Universität Heidelberg
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:
and, for m > 2,
where #nA. (x1….. xn) = A(x1) + A(xn)(We identify  with , 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 ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1.
• MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1.
• MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1.
The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable 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 ODDnB 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(nA) = {SS can be decided with n sequential queries to A}.
Q (nA) = {S : S 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:
• Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ …
Q (0, A) ⊂ Q (1, A) ⊂ Q (2, A) ⊂ …
The same is true if A is a jump.

Publication Date
Publisher Statement
Copyright 2000. Association for Symbolic Logic
Citation Information
Richard Beigel, William Gasarch, Martin Kummer, Timothy H. McNicholl, et al.. "The complexity of ODDnA" The Journal of Symbolic Logic Vol. 65 Iss. 1 (2000) p. 1 - 18
Available at: