The Complexity of ODDnA and MODmnA
William I. Gasarch, Georgia A. Martin · Birkhäuser Boston eBooks · 1999
Recall that, for n ≥ 1, ODD is the set of n-tuples (x 1 ,…,x n ) such that # (x 1 ,…,x n ) is odd: $${\rm{ODD}}_n^A = \left\{ {\left( {{x_1}, \ldots ,{x_n}} \right):\# _n^A\left( {{x_1}, \ldots ,{x_n}} \right){\rm{is}}\,{\rm{odd}}{\rm{.}}} \right\}$$ Clearly, ODD ∈ QC∥(n,A). If A = K or A is semirecursive, then (by Theorems 2.1.4 and 4.3.2.2, respectively) $${\rm{ODD}}_{{2^n} - 1}^A \in {\rm{Q}}\left( {n,A} \right)$$ , hence $${\rm{ODD}}_{{2^n}}^A \in {\rm{Q}}\left( {n + 1,A} \right)$$ . Can we do better than this for such A? What about other types of sets A? In this chapter we show the following.