Talk:RP (complexity)
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Computer science. | |
| ??? | This article has not yet received a rating on the assessment scale. | |
| ??? | This article has not yet received an importance rating on the assessment scale. | |
Contents |
[edit] 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.
[edit] 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)
[edit] 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 (UTC)
[edit] MAYBE
Perhaps it would make the article clearer if we defined RP using YES and MAYBE, i.e.
- If the correct answer is NO, it always returns MAYBE
- 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)
[edit] 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)
