Relativized Questions Involving Probabilistic Algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Relativized Questions Involving Probabilistic Algorithms

Full text

Pdf (435 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 1 (January 1982) table of contents

Pages: 261 - 268

Year of Publication: 1982

ISSN:0004-5411

Author

Charles Rackoff

Department of Computer Science, University of Toronto, Toronto, Ontario, Canada M5S 1A7

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 18, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322290.322306 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Leonard Adleman , Kenneth Manders, Reducibility, randomness, and intractibility (Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.151-163, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803405]
	2	BAKER, T, GILL, J, AND SOLOVAY, R Relativizatlons of the P -- Np quesUon SIAM J Comput 4 (1975), 431--442.
	3	BAKER, T. AND SELMAN, A A second step toward the polynom,al hierarchy. 17th Ann IEEE Syrup on Foundations of Computer Science, Houston, Texas, 1976, pp. 71-75
	4	BENNETT, C H., AND GILh J Relative to a random oracle A, P~ # NPa # CO-NPA with probability I SIAM J Comput. I0 (1981), 96-113
	5	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	6	GILL, J Computauonal complexity of probabthstlC Turmg machines. SIAM Z Comput. 6 (1977), 675-695. Also unpublished manuscript, Forschungsmshtut fur Mathemauk, Eldgenosslsche Techn- ~sche Hochschule, Zurich, 1976.
	7	Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
	8	LADNER, R., AND LYNCH, N RelauvlzaUon of questions about log space computabihty Math Syst. Theory 10 (1976), 19-32
	9	MILLER, G L Riemann's hypothesis and tests for primahty J Comput. Syst. Sct., 13 (1976), 300- 317
	10	Charles Rackoff, Relativized questions involving probabilistic algorithms, Proceedings of the tenth annual ACM symposium on Theory of computing, p.338-342, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804363]
	11	SOLOVA~,R., AND STRASSEN, V A fast Monte-Carlo test for pramality SlAM J Comput 6 (1977), 84-85
	12	STOCKMEYER L J.The polynomml tune hierarchy Theor Comput Sci 3 (1976), 1-22
	13	VALIANT, L.Relatwe complexity of checkmg and evaluating lnf Proc 5 (1976), 20-23

CITED BY 6

	Stuart A. Kurtz , Stephen R. Mahaney , James S. Royer, The isomorphism conjecture fails relative to a random oracle, Journal of the ACM (JACM), v.42 n.2, p.401-420, March 1995
	L G Valiant , V V Vazirani, NP is as easy as detecting unique solutions, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.458-463, May 06-08, 1985, Providence, Rhode Island, United States
	S. A. Kurtz , S. R. Mahaney , J. S. Royer, The ismorphism conjecture fails relative to a random oracle, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.157-166, May 14-17, 1989, Seattle, Washington, United States
	Ker-I Ko, Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy, Journal of the ACM (JACM), v.37 n.2, p.415-438, April 1990
	Richard Beigel , Harry Buhrman , Lance Fortnow, NP might not be as easy as detecting unique solutions, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.203-208, May 24-26, 1998, Dallas, Texas, United States
	Lance Fortnow , John D. Rogers, Separability and one-way functions, Computational Complexity, v.11 n.3/4, p.137-157, March 2003