Talk:RL (complexity)

What does RLP stand for. We need the full terminiology--Light current 23:51, 12 May 2006 (UTC)

Do we need this article?

Since 2006, no one fond references to support this article.. So, I move the content here. Please, find the references and explain the sense of abbreviation RLP in this case, because I suspect, the content happened to be entitled RLP by error. What should we do with such an article? dima (talk) 03:33, 13 July 2008 (UTC)

This is a very common complexity class, but it's more commonly described as RL rather than RLP. The later name is less commonly used but was chosen for the purpose of differentiation. But this just confused everyone, so now it's at RL. Dcoetzee 07:52, 14 July 2008 (UTC)

Dcoetzee, could you explain please, why do you call it RL? Who had published a description, using this abbreviatiore? Could you type please the section History, something like "The term RL is abbreviation of worls Relovative Labeling. First this ppreviation appears in famous publications by J.Smith and I.Fisher and J.Hunter (cite1, cite2); then, the approach was developed by A.Red, B.Brown and C.Green (cite3,cite4,cite5)..."; in y.2009, E.Black patented the ... based on ideas of RL (cite6), then G.Blanche got his Nobel Price (cite 7) for the theorem on minimal quantization on the compact RL sets (cite 8)"... I type this abracadabra to explain, how should you show that the subject is important, interesting and the future progress of Science cannot occur without development of this topic. dima (talk) 09:41, 14 July 2008 (UTC)

I know how to cite things. I hadn't gotten around to it. I'll add some stuff. Dcoetzee 10:54, 14 July 2008 (UTC)

Dcoetzee, now I see, that R means "random" and L means "logarithmic". I put the definition of the abbreviation first.
In the following, the constant 1/3 appears in the definition; then is happens, that the constant is arbirtrary. Please, give it some usual name and explain, why value 1/3 is of special interest. dima (talk) 23:37, 14 July 2008 (UTC)

1/3 is just the constant typically used in the definition, because it's a convenient simple fraction that satifies 0 < p < 1/2. A formal definition has to select some constant, and it's pedagogically better to introduce the concept with a single concrete value than with a class of equivalent definitions. A number of other randomized classes use similar definitions. I don't feel like this needs to be justified. Dcoetzee 01:30, 15 July 2008 (UTC)

I've also removed some incorrect facts you added - RLP does not stand for Randomized Logarithmic-space Problems, and there's no reason to believe Stanford invented the abbreviation RL (I have no idea who did). Complexity Zoo is just a list of facts and references, and is not a primary or original source for any material. You have a right to demand references, but please refrain from inventing facts without sources. Dcoetzee 01:33, 15 July 2008 (UTC)

Yes, Dcoetzee, I had typed more than I know; I tried to reveal meaning of R in the abbrevaition and my guess was wrong; thank you for cleaning. The article becomes readable. Could you do the same, please, with NL (complexity) (Why N and why L). Could you provide at least one reference that uses abbreviation RLP? I believe you have, and I already mention the article in the RLP disambig... dima (talk) 10:57, 15 July 2008 (UTC)

I can, yes, that's a good idea. Dcoetzee 18:37, 15 July 2008 (UTC)