Talk:ZPP (complexity)

Wrong definition

I think the definition is wrong on this page; machines recognizing languages in ZPP should always terminate in polynomial time, since machines recognizing languages in RP (and co-RP) do. This may be an alternate definition, but it's not consistent with the RP article. Can someone confirm this? Deco 20:17, 5 Nov 2004 (UTC)

(I edited the above to disambig the RP link. — Felix the Cassowary 10:50, 15 August 2005 (UTC))

• There are two definitions: one in style of the RP article and this one. They are equivalent, some sources use one, some other. I will add the other definition to this article. Andris 22:44, Nov 5, 2004 (UTC)

• I understand this better now. I think the proof I added helps illuminate the connection. Deco 07:11, 24 May 2005 (UTC)

More definitions

I added a definition based on witnesses. This is a extension of seeing NP as guess-and-check, providing a P-time verifier to which the deux ex machina decides (correctly) the non-deterministic choices. I think this adds an important intuition for RP problems. This intuition is also provided by allow the Turing Machine to say I Don't Know, or to have 1-Sided Error, but these seem to be properties of the TM, not of the problem, and it might be helpful to emphasize that the complexity is inherent in the problem.

I also personally like the shocking notion that a random string is likely to be a proof. That does say something about the problem. 192.31.89.40 14:26, 18 April 2007 (UTC) Ozga 14:27, 18 April 2007 (UTC)

About the proof of ZPP=RP AND coRP: LV algorithm error

It seems a small mistake: since RP has no false positive(if L is not in RP, RP will return NO definitely), I changed the LV algorithm in the part of proof "RP AND coRP is contained in ZPP".

original:Given an input in L, run A on the input. If it returns YES, the answer must be YES. Otherwise, run B on the input. If it returns NO, the answer must be NO. If neither occurs, repeat this step.

current:Given an input in L, run A on the input. If it returns NO, the answer must be NO, since RP has no false positive. Otherwise, run B on the input. If it returns YES, the answer must be YES, since coRP has no false negative. If neither occurs, repeat this step.

My fault. The original one is correct.

--Jarodwen (talk) 06:04, 17 April 2008 (UTC)

You're incorrect. The proof was correct before. RP has no false positive - that is, a positive result (a "YES") must be accurate. This is just what it originally said. Dcoetzee 06:28, 17 April 2008 (UTC)

An example of a language in ZPP but not in P

A nice addition to this article would be providing an example of a problem known to be in ZPP but which isn't known to be in P. The article Quadratic_residue#Prime_or_prime_power_modulus seems to provide one such example, but I am not familiar enough with the subject to confidently include it in this article myself. Deansg (talk) 19:09, 23 November 2018 (UTC)