Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T15:47:10.612Z Has data issue: false hasContentIssue false

The complexity of ODDnA

Published online by Cambridge University Press:  12 March 2014

Richard Beigel
Affiliation:
Department of Eecs (M/C 154), University of Illinois at Chicago, 851 S. Morgan St. - 1120 Seo, Chicago. IL, 60607-7053U.S.A., E-mail: beigel@uic.edu
William Gasarch
Affiliation:
Department of Computer Science, and Institute For Advanced Computing Studies, University of Maryland, College Park. MD 20742, U.S.A., E-mail: gasarch@cs.umd.edu
Martin Kummer
Affiliation:
Technische Universität Chemnitz-Zwickau, Fakultät Für Informatik, StraΒe Der Nationen 62, 09107 Chemnitz, Germany, Eu, E-mail: martin.kummer@informatik.tu-chemnitz.de
Georgia Martin
Affiliation:
12602 Goodhill Road, Wheaton, MD 20906, U.S.A.
Timothy Mcnicholl
Affiliation:
Department of Mathematics, University of Dallas, Irving, TX 75062, U.S.A., E-mail: tmcnicho@acad.udallas.edu
Frank Stephan
Affiliation:
Mathematisches Institut, Universität Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, GermanyEU, E-mail: fstephan@math.uni-heidelberg.de

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:

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(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) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ …

Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ …

The same is true if A is a jump.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable