On the robustness of ALMOST-$ℛ$
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 2, pp. 123-133.
@article{ITA_1996__30_2_123_0,
author = {Book, Ronald V. and Mayordomo, Elvira},
title = {On the robustness of {ALMOST-}$\mathcal {R}$
},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {123--133},
publisher = {EDP-Sciences},
volume = {30},
number = {2},
year = {1996},
zbl = {0860.68049},
mrnumber = {1420687},
language = {en},
url = {http://www.numdam.org/item/ITA_1996__30_2_123_0/}
}
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
DA  - 1996///
SP  - 123
EP  - 133
VL  - 30
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1996__30_2_123_0/
UR  - https://zbmath.org/?q=an%3A0860.68049
UR  - https://www.ams.org/mathscinet-getitem?mr=1420687
LA  - en
ID  - ITA_1996__30_2_123_0
ER  - 
Book, Ronald V.; Mayordomo, Elvira. On the robustness of ALMOST-$\mathcal {R}$
. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 2, pp. 123-133. http://www.numdam.org/item/ITA_1996__30_2_123_0/

[Am-86]K. Ambos-Spies, Randomness, relativizations, and polynomial reducibilities, Proc. First Conf. on Structure in Complexity Theory, 1986, pp. 23-34. | MR 854888 | Zbl 0615.03024

[BG-81]C. H. Bennett and J. Gill, Relative to a random oracle A, PA ≠ NPA ࣔ co - NPA with probability 1, SIAM Journal on Computing, 1981, 10, pp. 96-113. | MR 605606 | Zbl 0454.68030

[Bo-94]R. Book, On languages reducible to algorithmically random languages, SIAM Journal on Computing, 1994, 23, pp. 1275-1282. | MR 1303336 | Zbl 0834.68027

[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. | MR 1264386 | Zbl 0819.68056

[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.

[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. | MR 990050 | Zbl 0668.68052

[Hi-78] Hinman, Recursion-Theoretic Hierarchies, Springer-Verlag, 1978. | MR 499205 | Zbl 0371.02017

[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. | MR 1320211 | Zbl 0827.68043

[Ka-911] S. Kautz, Degrees of Random Sets, Ph. D. Dissertation, Cornell University, 1991. | MR 2686787

[Ka-94] S. Kautz, An improved zero-one law for algorithmically random sequences , submitted. | Zbl 0897.68046

[Ku-81] S. Kurtz, Randomness and Genericity in the Degrees of Unsolvability, Ph. D. Dissertation, University of Illinois at Urbana-Champaign, 1981. | MR 2631709

[Lu-92] J. Lutz, Almost-everywhere high nonuniform complexity, J. Comput. System. Sci., 1992, 25, pp. 130-143. | MR 1160462 | Zbl 0767.68043

[Ma-66] P. Martin-Lof, On the definition of infinite random sequences, Info. and Control, 1966, 9, pp. 602-619. | MR 223179 | Zbl 0244.62008

[NW-88] N. Nisan and A. Wigderson, Hardness versus randomness, Proc. 29th Symp. on Foundations of Computer Science, 1988, pp. 2-11.

[Ro-67] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. | MR 224462 | Zbl 0183.01401

[TB-91] S. Tang and R. V. Book, Polynomial-time reducibilities and "Almost-all" oracle sets, Theoretical Computer Science, 1991, 81, pp. 36-47. | MR 1103097 | Zbl 0719.03020