×

zbMATH — the first resource for mathematics

Distinguishing conjunctive and disjunctive reducibilities by sparse sets. (English) Zbl 0681.68066
Summary: 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)
PDF BibTeX XML Cite
Full Text: DOI
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.