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.


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


[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.