On the robustness of ALMOST- ℛ

Ronald V. Book; Elvira Mayordomo

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

  • Volume: 30, Issue: 2, page 123-133
  • ISSN: 0988-3754

How to cite

top

Book, Ronald V., and Mayordomo, Elvira. "On the robustness of ALMOST-$\mathcal {R}$." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.2 (1996): 123-133. <http://eudml.org/doc/92528>.

@article{Book1996,
author = {Book, Ronald V., Mayordomo, Elvira},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {ALMOST-; reducibility},
language = {eng},
number = {2},
pages = {123-133},
publisher = {EDP-Sciences},
title = {On the robustness of ALMOST-$\mathcal \{R\}$},
url = {http://eudml.org/doc/92528},
volume = {30},
year = {1996},
}

TY - JOUR
AU - Book, Ronald V.
AU - Mayordomo, Elvira
TI - On the robustness of ALMOST-$\mathcal {R}$
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 2
SP - 123
EP - 133
LA - eng
KW - ALMOST-; reducibility
UR - http://eudml.org/doc/92528
ER -

References

top
  1. [Am-86] K. AMBOS-SPIES, Randomness, relativizations, and polynomial reducibilities, Proc. First Conf. on Structure in Complexity Theory, 1986, pp. 23-34. Zbl0615.03024MR854888
  2. [BG-81] C. H. BENNETT and J. GILL, Relative to a random oracle A, PA ≠ NPA &#2260; co - NPA with probability 1, SIAM Journal on Computing, 1981, 10, pp. 96-113. Zbl0454.68030MR605606
  3. [Bo-94] R. BOOK, On languages reducible to algorithmically random languages, SIAM Journal on Computing, 1994, 23, pp. 1275-1282. Zbl0834.68027MR1303336
  4. [BLW-94] R. BOOK, J. LUTZ and K. WAGNER, An observation on probability versus randomness with applications to complexity classes, Math. Systems Theory, 1994, 27, pp. 201-209. Zbl0819.68056MR1264386
  5. [BM-95] H. BUHRMAN and E. MAYORDOMO, An excursion to the Kolmogorov randomstrings, Proc. Tenth Conf. on Structure in Complexity Theory, 1995, pp. 197-203. 
  6. [Ca-89] J. CAI, With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, J. Comput. System. Sci., 1989, 38, pp. 68-85. Zbl0668.68052MR990050
  7. [Hi-78] HINMAN, Recursion-Theoretic Hierarchies, Springer-Verlag, 1978. Zbl0371.02017MR499205
  8. [JL-95] D. W. JUEDES and J. H. LUTZ, The complexity and distribution of hard problems, SIAM Journal on Computing, 1995, 24, pp. 279-295. Zbl0827.68043MR1320211
  9. [Ka-911] S. KAUTZ, Degrees of Random Sets, Ph. D. Dissertation, Cornell University, 1991. MR2686787
  10. [Ka-94] S. KAUTZ, An improved zero-one law for algorithmically random sequences , submitted. Zbl0897.68046
  11. [Ku-81] S. KURTZ, Randomness and Genericity in the Degrees of Unsolvability, Ph. D. Dissertation, University of Illinois at Urbana-Champaign, 1981. MR2631709
  12. [Lu-92] J. LUTZ, Almost-everywhere high nonuniform complexity, J. Comput. System. Sci., 1992, 25, pp. 130-143. Zbl0767.68043MR1160462
  13. [Ma-66] P. MARTIN-LOF, On the definition of infinite random sequences, Info. and Control, 1966, 9, pp. 602-619. Zbl0244.62008MR223179
  14. [NW-88] N. NISAN and A. WIGDERSON, Hardness versus randomness, Proc. 29th Symp. on Foundations of Computer Science, 1988, pp. 2-11. 
  15. [Ro-67] H. ROGERS, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. Zbl0183.01401MR224462
  16. [TB-91] S. TANG and R. V. BOOK, Polynomial-time reducibilities and "Almost-all" oracle sets, Theoretical Computer Science, 1991, 81, pp. 36-47. Zbl0719.03020MR1103097

NotesEmbed ?

top

You must be logged in to post comments.