×

zbMATH — the first resource for mathematics

Reducibilities on tally and sparse sets. (English) Zbl 0731.68039
Summary: Classes of sets that are inter-reducible to tally sets by polynomial-type computable reducibilities are studied.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] 1. E. ALLENDER and R. RUBINSTEIN, P-printable sets, S.I.A.M. J. Comput., 1988, 17, pp. 1193-1202. Zbl0682.68039 MR972668 · Zbl 0682.68039
[2] 2. E. ALLENDER and O. WATANABE, Kolmogorov complexity and degrees of tally sets, Inform. and Comput., 1990, 86, pp. 160-178. Zbl0704.03023 MR1054537 · Zbl 0704.03023
[3] 3. T. BAKER, J. GILL and R. SOLOWAY, Relativizations of the P = ? NP question, S.I.A.M. J. Comput., 1975, 4, pp. 431-442. Zbl0323.68033 MR395311 · Zbl 0323.68033
[4] 4. J. BALCÁZAR and R. BOOK, Sets with small generalized Kolmogorov complexity, Acta Inform., 1986, 23, pp. 679-688. Zbl0616.68046 MR865501 · Zbl 0616.68046
[5] 5. J. BALCÁZAR, J. DÍAZ and J. GABARRÓ, Structural Complexity, I and II, Springer-Verlag, 1988, and 1990. Zbl0638.68040 MR1047862 · Zbl 0638.68040
[6] 6. R. BOOK and K. KO, On sets truth-table reducible to sparse sets, S.I.A.M. J. Comput., 1988, 77, pp. 903-919. Zbl0665.68040 MR961047 · Zbl 0665.68040
[7] 7. J. HARTMANIS, N. IMMERMAN and V. SEWELSON, Sparse sets in NP-P: EXPTIME versus NEXPTIME, Proc. 15th A.C.M. Symp. Theory of Computing, 1983, pp. 382-391. · Zbl 0586.68042
[8] 8. K. KO, Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity, 1985, 1, pp. 210-231. Zbl0609.03015 MR925429 · Zbl 0609.03015
[9] 9. K. KO, Distinguishing bounded reducibilities by sparse sets, Inform. and Comput., 1989, 81, pp. 62-87. Zbl0681.68066 MR992304 · Zbl 0681.68066
[10] 10. R. LANDER, N. LYNCH and A. SELMAN, A comparison of polynomial-time reducibilities, Theoret. Comput. Sci., 1975, 1, pp. 103-123. Zbl0321.68039 MR395319 · Zbl 0321.68039
[11] 11. T. LONG, Strong nondeterministic polynomial-time reducibilites, Theoret. Comput. Sci., 1982, 21, pp. 1-25. Zbl0521.03028 MR672099 · Zbl 0521.03028
[12] 12. T. LONG, On restricting the size of oracles compared with restricting access to oracles, S.I.A.M. J. Comput., 1985, 14, pp. 585-597. Zbl0583.68025 MR795932 · Zbl 0583.68025
[13] 13. U. SCHÖNING, Complexity and Structure, L.N.C.S., No. 211, 1986, Springer-Verlag Publ. Co. Zbl0589.03022 MR827009 · Zbl 0589.03022
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.