The complexity of ODD_n~A

摘要

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~4(x_1, …, x_n) is odd} and, for m ≥ 2. MODm_n~A = {(x_1, …, x_n):#_n~A(x_1, …, x_n) not ≡ 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 n - 1. ·ODD_n~A can be decided with [log(n + 1)] sequential queries to A but not with [log(n + 1)] - 1. ·MODm_n~A can be decided with[n/m] + [n/m] parallel queries to A but not with [n/m] + [n/m] - 1. ·MODm_n~A 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 bonds 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 ODD_n~A cannot be decided with n - 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODD_n~B)n 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 recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: ·Q(0, A) is contained in Q(1, A) is contained in Q(2, A) is contained in … ·Q_‖(0, A) is contained in Q_‖(1, A) is contained in Q_‖(2, A) is contained in … The same is true if A is a jump.