Reducibilities on tally and sparse sets
Tang, Shouwen ; Book, Ronald V.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 293-302 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1991__25_3_293_0,
     author = {Tang, Shouwen and Book, Ronald V.},
     title = {Reducibilities on tally and sparse sets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {25},
     year = {1991},
     pages = {293-302},
     mrnumber = {1119046},
     zbl = {0731.68039},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1991__25_3_293_0}
}

Tang, Shouwen; Book, Ronald V. Reducibilities on tally and sparse sets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) pp. 293-302. http://gdmltest.u-ga.fr/item/ITA_1991__25_3_293_0/

1. E. Allender and R. Rubinstein, P-printable sets, S.I.A.M. J. Comput., 1988, 17, pp. 1193-1202. | MR 972668 | Zbl 0682.68039

2. E. Allender and O. Watanabe, Kolmogorov complexity and degrees of tally sets, Inform. and Comput., 1990, 86, pp. 160-178. | MR 1054537 | Zbl 0704.03023

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. | MR 395311 | Zbl 0323.68033

4. J. Balcázar and R. Book, Sets with small generalized Kolmogorov complexity, Acta Inform., 1986, 23, pp. 679-688. | MR 865501 | Zbl 0616.68046

5. J. Balcázar, J. Díaz and J. Gabarró, Structural Complexity, I and II, Springer-Verlag, 1988, and 1990. | MR 1047862 | Zbl 0638.68040

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. | MR 961047 | Zbl 0665.68040

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.

8. K. Ko, Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity, 1985, 1, pp. 210-231. | MR 925429 | Zbl 0609.03015

9. K. Ko, Distinguishing bounded reducibilities by sparse sets, Inform. and Comput., 1989, 81, pp. 62-87. | MR 992304 | Zbl 0681.68066

10. R. Lander, N. Lynch and A. Selman, A comparison of polynomial-time reducibilities, Theoret. Comput. Sci., 1975, 1, pp. 103-123. | MR 395319 | Zbl 0321.68039

11. T. Long, Strong nondeterministic polynomial-time reducibilites, Theoret. Comput. Sci., 1982, 21, pp. 1-25. | MR 672099 | Zbl 0521.03028

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. | MR 795932 | Zbl 0583.68025

13. U. Schöning, Complexity and Structure, L.N.C.S., No. 211, 1986, Springer-Verlag Publ. Co. | MR 827009 | Zbl 0589.03022