On the robustness of ALMOST-ℛ
Book, Ronald V. ; Mayordomo, Elvira
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 123-133 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1996-01-01
@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},
     volume = {30},
     year = {1996},
     pages = {123-133},
     mrnumber = {1420687},
     zbl = {0860.68049},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1996__30_2_123_0}
}

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) pp. 123-133. http://gdmltest.u-ga.fr/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