Reducibilities on tally and sparse sets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 3, pp. 293-302.
@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},
     pages = {293--302},
     publisher = {EDP-Sciences},
     volume = {25},
     number = {3},
     year = {1991},
     mrnumber = {1119046},
     zbl = {0731.68039},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1991__25_3_293_0/}
}
TY  - JOUR
AU  - Tang, Shouwen
AU  - Book, Ronald V.
TI  - Reducibilities on tally and sparse sets
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1991
SP  - 293
EP  - 302
VL  - 25
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1991__25_3_293_0/
LA  - en
ID  - ITA_1991__25_3_293_0
ER  - 
%0 Journal Article
%A Tang, Shouwen
%A Book, Ronald V.
%T Reducibilities on tally and sparse sets
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1991
%P 293-302
%V 25
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1991__25_3_293_0/
%G en
%F 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) no. 3, pp. 293-302. http://archive.numdam.org/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 | Zbl

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

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 | Zbl

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

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

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 | Zbl

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 | Zbl

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

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

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

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 | Zbl

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