The complexity of ODD_n^A

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The authors consider oracle Turing machine computations where the complexity of the reduction is measured by the number of oracle queries asked for any fixed input. For an introduction to the corresponding area of bounded queries in recursion theory see the survey by \textit{W.~Gasarch} and \textit{F.~Stephan} [in: S. B. Cooper et al. (eds.), Models and computability. Invited papers of the Logic Colloquium '97. Lond. Math. Soc. Lect. Note Ser. 259, 117-156 (1999; Zbl 0944.03031)] and the textbook by \textit{W.~Gasarch} and \textit{G. A. Martin}, [Bounded queries in recursion theory (Birkhäuser, Boston) (1999; Zbl 0936.03038)]. For natural numbers \(n\geq 1\) and \(m\geq 2\) and for a set \(A\) (sets are always understood as sets of natural numbers), let \(\text{MODm}_n^A\) denote the set that contains exactly the (appropriately encoded) \(n\)-tuples \((x_1, \ldots, x_n)\) such that the number of indices \(k\) with \(x_k\) in \(A\) is not a multiple of \(m\). The set \(\text{ MOD2}_n^A\) is also called \(\text{ ODD}_n^A\), i.e., any \(n\)-tuple is in \(\text{ ODD}_n^A\) if and only if an odd number of its components is in \(A\). Main results of the paper are the following. First fix natural numbers \(n\) and~\(m\) as above and assume that \(A\) is a nonrecursive semirecursive set or is a jump . Then in the oracle Turing machine model where the queries have to be asked in parallel, the set \(\text{ ODD}_n^A\) can be decided with \(n\) queries to \(A\) but not with \(n-1\) queries. For the set \(\text{ MODm}_n^A\) the corresponding bound on the number of parallel queries is \(\lceil n/m \rceil + \lfloor n/m \rfloor\). For both sets,similar tight bounds can be derived in the sequential query model. Second, assume that \(A\) is not recursive but is semirecursive or recursively enumerable. Then in the sequential as well as in the parallel query model, for any natural number \(n\) strictly more sets can be decided with \(n+1\) queries to the oracle \(A\) than just with \(n\) queries, i.e., in both computation models we obtain a non-collapsing hierarchy with respect to the constant that bounds the number of queries.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: The complexity of ODD_n^A

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4953205)

The complexity of ODDnA

The complexity of ODD_n^A