A zero one law for RP

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Russell Impagliazzo Articles by Philippe Moser

18th Annual IEEE Conference on Computational Complexity (CCC'03)

Aarhus, Denmark

July 07-July 10

ISBN: 0-7695-1879-6

	ASCII Text	x
	Russell Impagliazzo, Philippe Moser, "A zero one law for RP," Computational Complexity, Annual IEEE Conference on, pp. 48, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.

	BibTex	x
	@article{ 10.1109/CCC.2003.1214409, author = {Russell Impagliazzo and Philippe Moser}, title = {A zero one law for RP}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2003}, issn = {1093-0159}, pages = {48}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214409}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - A zero one law for RP SN - 1093-0159 SP EP A1 - Russell Impagliazzo, A1 - Philippe Moser, PY - 2003 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Russell Impagliazzo

Philippe Moser

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214409

In this paper we show that if RP has p-measure non zero then ZPP = EXP. As corollaries we obtain a zero-one law for RP, and that both probabilistic classes ZPP and RP have the same p-measure. Finally we prove that if NP has p-measure non zero then NP = AM.

Citation:

Russell Impagliazzo, Philippe Moser, "A zero one law for RP," ccc, pp.48, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.