One query reducibilities between partial information classes

A partial information algorithm for a language A computes for m input words (x1,…,xm) a set of bitstrings containing χA(x1,…,xm). For a family D of sets of bitstrings of length m, A∈P[D] if there is a polynomial time partial information algorithm that always outputs a set from D. For the case m=2 we investigate whether for families D1 and D2 the languages in P[D1] are reducible to languages in PX[D2] for some X in the Polynomial Hierarchy PH or in EXP. Several non-reducibilities follow from known structural properties of classes P[D]. Beigel et al. [Membership comparable and p-selective sets, Technical Report 2002-006N, NEC Research Institute, 2002] showed non-reducibility from strongly 2-membership comparable languages to p-selective languages. They also showed one query (1-tt, for short) reducibility from 2-cheatable languages to p-selective languages. A proof of Tantau [Combinatorial representations of partial information classes and their truth-table closures, Master's Thesis, TU Berlin, Germany, 1999] yields a 1-tt reducibility from 2-cheatable languages to languages in PΣ2p[MIN2]. We achieve results for all remaining non-trivial pairs of classes P[D] for m=2. Our positive results all show 1-tt reducibilities. Our negative results even hold if the reducing machines as well as the partial information algorithms for the languages we try to reduce to have access to oracles in EXP. We show: