With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Full text

Pdf (569 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 21 - 29

Year of Publication: 1986

ISBN:0-89791-193-8

Author

J Y Cai

Computer Science Department, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 31, 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/12130.12133 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.

	BGS	T.Baker, J.Gill and R.Solovay, "Relativization of P=?NP question", SIAM J. on Computing 4 (1975), 431- 442
	BS	T.Baker and A.Selman, "A second step toward the polynomial hierarchy", Theretical Computer Science 8 (1979), 177-187
	BG	C.Bennet and J.Gill, "Relative to a reandom oracle A, pA~NpA~eco-NPA with probability 1", SIAM d. on Computing 10 (1981), 96-113
	CKS	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	FSS	M.Furst, J.Saxe and M.Sipser, "Parity, circuits and the polynomial time hierarchy", Proe. of 22 nd FOCS, 1981,260-270
	MS	A.Meyer and L.Stoekmeyer, "The equivalence problem for regular expressions with squaring requires exponetial space, " Proc. of 13th Ann. IEEE Sym. on Switching & Aut. Th. 1972, 125-129
	St	L.Stockmeyer, "The polynomial-time hierarchy", Theo. Comp. Se. 3 (1977) 1-22
	Y1	A. Yao, "Lower bounds by probabitistie arguments". Proc. of24th FOCS, 1983
	Y2	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

CITED BY 6

	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States
	J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States
	Paul Beame , Russell Impagliazzo , Jan Krajíček , Toniann Pitassi , Pavel Pudlák , Alan Woods, Exponential lower bounds for the pigeonhole principle, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.200-220, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	Jin-Yi Cai , Osamu Watanabe, Relativized collapsing between BPP and PH under stringent oracle access, Information Processing Letters, v.90 n.3, p.147-154, 16 May 2004
	Gerry Eisman , B. Ravikumar, Approximate recognition of non-regular languages by finite automata, Proceedings of the Twenty-eighth Australasian conference on Computer Science, p.219-227, January 01, 2005, Newcastle, Australia