A zero one law for RP

Aarhus, Denmark July 07-July 10

DOI Bookmark:

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

18th Annual IEEE Conference on Comput ...

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

	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

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.