Talk:RP (complexity)

A problem?

I think, there is a shortcoming to the explanation:

The probability have to be greater than zero and strictly smaller than one to generate the exacatly same class.

Ugly formula

Hey all, I introduced an ugly formula as part of an edit. I believe the formula is correct, but it doesn't look good inline. Can someone more format-gifted fix this up to look better?

(the formula is right because the more times the algorithm gives "NO" the more certain we are that is the actual answer - therefore it is not (1/2)^n, which approaches zero as n is large, but 1-(1/2)^n which approaches 1.

-- JustinWick 15:27, May 16, 2005 (UTC)

I did some HTML. Now it looks kinda weird, but I think it's still unambiguous. Deco 00:36, 17 May 2005 (UTC)

YES and NO mixups

Wow, I feel like an idiot. Maybe this article is just somewhat confusing, but for a minute I wasn't connecting that "always correct on NO instances" is equivalent to "always correct when it yields YES". Sorry for my misedit, and I hope someone can help clarify this. Deco 09:14, 19 May 2005 (UT

I agree the phrasing is a little confusing. If anyone can think of a way to clarify, it would certainly improve the article. 75.82.133.73 (talk) 06:15, 16 December 2008 (UTC)

MAYBE

Perhaps it would make the article clearer if we defined RP using YES and MAYBE, i.e.

1. If the correct answer is NO, it always returns MAYBE
2. If the correct answer is YES, then it returns YES with probability at least 1/2, otherwise MAYBE.

A return value of YES means the correct answer is certainly YES, and a return value of MAYBE means the correct answer could be either YES or NO. If the algorithm is run many times and returns a MAYBE every time, this supports the hypothesis that the answer is NO but does not constitute proof. In this sense, if the correct answer is NO then the algorithm is unable to prove it so.

Similarly we can define Co-RP using NO and MAYBE.

What do you reckon - is this definition clearer or not?

This is an interesting idea, and it does fit in with how the algorithms usually work (either establish proof of YES or else just say you're not sure). We could eliminate all the language referring to the algorithm being "wrong", which is sort of weird. But I'd like to see what others think, since the treatment here is somewhat traditional. Deco 01:07, 20 May 2005 (UTC)

I think the MAYBE treatment would fit poorly with the analysis of repeated runs, which characterizes an algorithm's likely correctness versus other things that could compromise the result. --Davidstrauss 08:14, 1 September 2006 (UTC)

Renaming to RP (complexity theory)

Can I suggest that this article be renamed to RP (complexity theory), and the disambig moved here? I may be biased but complexity theory doesn't seem like it's the sort of thing that random people intend. Felix the Cassowary 12:05, 26 July 2005 (UTC)

• The argument could be made that the complexity class is the only thing on that list which is actually named "RP"; the other things are simply acronyms, many of which are very specialized, or not very plausible. However, I'm neutral to the move, since you're right that most people aren't looking for complexity theory. I would be happy to perform the move in a few days, if there is consensus. Please note that the resulting article should be called "RP (complexity)", not "RP (complexity theory)", to be in line with other complexity classes. -- Creidieki 15:06, 26 July 2005 (UTC)

• I'm going to have to concur with Cassowary. Many of the other uses of RP, while not the name proper of the subject, are very common abbreviations, and complexity theory isn't even mainstream within computer science. If we could do a visitor count somehow I'd bet more were looking for roleplaying. Deco 04:45, 27 July 2005 (UTC)

Challenging a statement

"The intersection of the sets RP and Co-RP is called ZPP"

I believe the intersection of a complexity class contains all problems in both classes. Thus, in the intersection we can guarantee that there exists both an algorithm that will determine (with certainty) that the answer is yes, and an algorithm that will determine (with certainty) that the answer is no. By running both algorithms (in polynomial time) we may determine with certainty the correct answer. Thus

"The intersection of the sets RP and Co-RP is called P" -- Yoderj 20:02, 25 October 2007 (UTC)

You're incorrect. The issue is that although either the RP or the co-RP algorithm will return the correct answer, if they return different answers, you don't know which one to trust. If you continually run them both until they produce the same answer, this will ensure that you have the right answer, and you only have to run them a constant number of times on average; this results in the expected-time polynomial-time algorithm usually used in the definition of ZPP. Dcoetzee 23:21, 27 October 2007 (UTC)

Polynomial identity testing

I believe this statement is incorrect:

A natural example of a problem in co-RP currently not known to be in P is the problem of deciding whether a given multivariate arithmetic expression over the integers is the zero-polynomial. For instance, x·x − y·y − (x + y)·(x − y) is the zero-polynomial while x·x + y·y is not.

The polynomial identity testing problem is normally defined over finite fields, with the polynomials specified by their coefficients, and the random assignment method of solution does not apply to polynomials over the integers. So I'll fix it. Dcoetzee 21:39, 5 February 2008 (UTC)

As far as I know, the standard definition of PIT is over the integers, not over a finite field. In any case, the randomized solution does work over the integers just fine. The heart of the algorithm is the Schwartz-Zippel lemma (i.e., evaluation of a nonzero multivariate poly of degree d over a finite subset S gives 0 with probability at most d/|S|), which works the same for arbitrary integral domains, finite or otherwise. As for polynomials over Z, depending on the chosen representation of the input polynomials there may arise a problem that the degree of the polynomial is exponential, hence the value of the polynomial (as well as the intermediate results) may have exponential size, which makes the randomized algorithm exponential time. This can be worked around by a simple trick (evaluate the polynomial modulo a suitable prime). You can find a nicely written exposition in this paper, for instance. -- EJ (talk) 12:13, 6 February 2008 (UTC)

In fact, it is for finite rings that the randomized algorithm does not work, because you need the degree of the polynomial to be smaller than the size of S (hence smaller than the size of the ring). The description which you put in BPP (complexity) is wrong for the same reason, the 2d bound (the constant 2 is arbitrary anyway) does not apply to the number of trials, but to the size of the sample set for the individual variables. -- EJ (talk) 12:32, 6 February 2008 (UTC)

One more remark: it is essential for PIT to be defined for some succint representation of polynomials (like arithmetic circuits or fomulas). If the input polynomial is represented explicitly by a list of coefficients and monomials, the problem is trivially solvable in P: over an infinite ring, a polynomial is identically zero iff all the coefficients are zero; over a finite field GF(q), you first reduce all exponents to be smaller than q using the identity x^q = x, join terms which have the same monomial after this transormation, and then check whether all coefficients are zero. -- EJ (talk) 13:09, 6 February 2008 (UTC)

I stand corrected — I didn't read my source carefully enough. Now that I look, it represents the polynomial to be evaluated as an oracle, applies to arbitrary fields, and 2d is the size of the subset (I also see why 2 is arbitrary - this only affects the constant bound of the probability). Sorry for the bold edits and thanks a lot for your feedback. Dcoetzee 19:19, 6 February 2008 (UTC)

Opinion in Summary

"So if the algorithm is run 100 times, then the chance of it giving the wrong answer every time is lower than the chance that cosmic rays corrupted the memory of the computer running the algorithm.[citation needed] In this sense, if a source of random numbers is available, most algorithms in RP are highly practical."

These two sentences (in the current version of the summary, 24 March 2011) contain nothing but opinion and should be removed. —Preceding unsigned comment added by Alex.atkins (talk • contribs) 14:32, 3 May 2011 (UTC)

Probabilities taken over what? Lacking quantifiers

Is the probability $1/2$ conditioned on any fixed YES instance, or can the probability be taken over the set of all YES instances?

In other words, could the algorithm be deterministic? Could half of YES instances deterministically return NO?

E.g. Is the following algorithm for deciding whether an integer $n$ is even in RP? If $2\not \mid n$ then return no; if $4\mid n$ then return yes; if $4\not \mid n$ and $2\mid n$ then return no. The algorithm is deterministic and returns NO for exactly half of YES instances.

Using quantifiers:

A language $L$ is in RP if and only if it satisfies the following conditions: There exists a polynomial time algorithm $f:\Sigma ^{*}\times [0,1]\to \{0,1\}$ such that:

• For all $x\in L$, $\Pr[f(x,r)=1\mid r\sim U(0,1)]\geq 1/2$
• For all $x\not \in L$, for all $r\in [0,1]$, $f(x,r)=0$

The article always appears to be consistent with another definition, not equivalent to the first: There exists a polynomial time algorithm $f:\Sigma ^{*}\times [0,1]\to \{0,1\}$ such that:

• $\Pr[f(x,r)=1\mid x{\text{ drawn randomly from }}L,r\sim U(0,1)]\geq 1/2$
• $\Pr[f(x,r)=0\mid x{\text{ drawn randomly from }}L^{c},r\sim U(0,1)]=1$

— Preceding unsigned comment added by 86.23.54.173 (talk) 00:42, May 29, 2018‎ (UTC)

The probability is over the internal randomness of the probabilistic Turing machine, not over inputs. The randomized algorithm is required, for every input in the language, to output 1 with probability greater than 1/2. --Robin (talk) 05:23, 3 June 2018 (UTC)