Reducibilities on tally and sparse sets

Shouwen Tang; Ronald V. Book

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1991)

  • Volume: 25, Issue: 3, page 293-302
  • ISSN: 0988-3754

How to cite

top

Tang, Shouwen, and Book, Ronald V.. "Reducibilities on tally and sparse sets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 25.3 (1991): 293-302. <http://eudml.org/doc/92394>.

@article{Tang1991,
author = {Tang, Shouwen, Book, Ronald V.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {sparse sets; complexity classes; tally sets; polynomial-type computable reducibilities},
language = {eng},
number = {3},
pages = {293-302},
publisher = {EDP-Sciences},
title = {Reducibilities on tally and sparse sets},
url = {http://eudml.org/doc/92394},
volume = {25},
year = {1991},
}

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
PB - EDP-Sciences
VL - 25
IS - 3
SP - 293
EP - 302
LA - eng
KW - sparse sets; complexity classes; tally sets; polynomial-type computable reducibilities
UR - http://eudml.org/doc/92394
ER -

References

top
  1. 1. E. ALLENDER and R. RUBINSTEIN, P-printable sets, S.I.A.M. J. Comput., 1988, 17, pp. 1193-1202. Zbl0682.68039MR972668
  2. 2. E. ALLENDER and O. WATANABE, Kolmogorov complexity and degrees of tally sets, Inform. and Comput., 1990, 86, pp. 160-178. Zbl0704.03023MR1054537
  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.68033MR395311
  4. 4. J. BALCÁZAR and R. BOOK, Sets with small generalized Kolmogorov complexity, Acta Inform., 1986, 23, pp. 679-688. Zbl0616.68046MR865501
  5. 5. J. BALCÁZAR, J. DÍAZ and J. GABARRÓ, Structural Complexity, I and II, Springer-Verlag, 1988, and 1990. Zbl0638.68040MR1047862
  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.68040MR961047
  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. Zbl0586.68042
  8. 8. K. KO, Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity, 1985, 1, pp. 210-231. Zbl0609.03015MR925429
  9. 9. K. KO, Distinguishing bounded reducibilities by sparse sets, Inform. and Comput., 1989, 81, pp. 62-87. Zbl0681.68066MR992304
  10. 10. R. LANDER, N. LYNCH and A. SELMAN, A comparison of polynomial-time reducibilities, Theoret. Comput. Sci., 1975, 1, pp. 103-123. Zbl0321.68039MR395319
  11. 11. T. LONG, Strong nondeterministic polynomial-time reducibilites, Theoret. Comput. Sci., 1982, 21, pp. 1-25. Zbl0521.03028MR672099
  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.68025MR795932
  13. 13. U. SCHÖNING, Complexity and Structure, L.N.C.S., No. 211, 1986, Springer-Verlag Publ. Co. Zbl0589.03022MR827009

NotesEmbed ?

top

You must be logged in to post comments.