Distinguishing conjunctive and disjunctive reducibilities by sparse sets

AbstractVarious polynomial-time truth-table reducibilities are compared by their ability of using sparse oracles to answer queries. The reducibilities studied here include conjunctive reducibility, bounded conjunctive reducibility, disjunctive reducibility, bounded disjunctive reducibility, truth-table reducibility, and bounded truth-table reducibility. For any two reducibilities ≤rP and ≤sP, we compare the class of sets ≤rP-reducible to sparse sets with the class of sets ≤sP-reducible to sparse sets. For most pairs of reducibilities ≤rP and ≤sP, it is shown that the two associated reduction classes are incomparable, unless a trivial inclusive relation holds