Ko, Ker-I Distinguishing conjunctive and disjunctive reducibilities by sparse sets. (English) Zbl 0681.68066 Inf. Comput. 81, No. 1, 62-87 (1989). 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. Cited in 2 ReviewsCited in 9 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity) 68Q05 Models of computation (Turing machines, etc.) (MSC2010) Keywords:oracle machines; reducibilities; sparse sets PDFBibTeX XMLCite \textit{K.-I Ko}, Inf. Comput. 81, No. 1, 62--87 (1989; Zbl 0681.68066) 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, (Inform. Proc. Lett., 16 (1983)), 55-60 · Zbl 0501.68014 [5] Hopcroft, J. E.; Ullman, J. D., (Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0426.68001 [6] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (Proceedings, 12th ACM Symposium on Theory of Computing (1980)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.