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))[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

"The running time is polynomial in expectation for every input"

This constraint is described like this in the introduction : "for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer"

The way I understood it at first, it's not a constraint at all, since, if you take a problem of size n that has average running time T, there are of course infinitely many polynomials p such that p(n) = T + 1. There's clearly something wrong in this sentence.

It seems to me like this would make more sense if it were "there is some polynomial p, such that, for all problems of size n, the average running time will be less than p(n)". Is it what is intended? Pripensanto (talk) 19:19, 9 November 2024 (UTC)[reply]