Distinguishing conjunctive and disjunctive reducibilities by sparse sets.

*(English)*Zbl 0681.68066Summary: Various 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 \(\leq^ P_ r\) and \(\leq^ P_ s\), we compare the class of sets \(\leq^ P_ r\)-reducible to sparse sets with the class of sets \(\leq^ P_ s\)-reducible to sparse sets. For most pairs of reducibilities \(\leq^ P_ r\) and \(\leq^ P_ s\), it is shown that the two associated reduction classes are incomparable, unless a trivial inclusive relation holds.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

03D15 | Complexity of computation (including implicit computational complexity) |

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

Full Text:
DOI

**OpenURL**

##### References:

[1] | BalcĂˇzar, J.; Book, R.V., Sets with small generalized Kolmogorov complexity, Acta inform., 23, 679-688, (1986) · Zbl 0616.68046 |

[2] | Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, 305-322, (1977) · Zbl 0356.68059 |

[3] | Book, R.V.; Ko, K., On sets truth-table reducible to sparse sets, SIAM J. comput., 17, 903-919, (1988) · Zbl 0665.68040 |

[4] | Hartmanis, J., On sparse sets in NP-P, (), 55-60 · Zbl 0501.68014 |

[5] | Hopcroft, J.E.; Ullman, J.D., () |

[6] | Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (), 302-309 |

[7] | Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial-time reducibilities, Theoret. comput. sci., 1, 103-123, (1975) · Zbl 0321.68039 |

[8] | Long, T., On restricting the size of oracles compared with sparse oracles, J. assoc. comput. Mach., 33, 618-627, (1986) |

[9] | Watanabe, O., A comparison of polynomial time completeness notions, Theoret. comput. sci., 54, 249-265, (1987) · Zbl 0635.68035 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.