Talk:RL

RL = NL?

This article claims that RL=NL. I believe this is not known to be true. The lecture notes cited here specifically say that RL is not known to equal NL. Therefore, I think this section should be removed. Comments?

RLP, which some authors call RL, is not known to equal NL. This RL is the class that Goldreich calls badRSPACE(log n), and his Proposition 6.1 is what I outline in the article. This is why the introduction is careful to point out this naming difference. Nevertheless, if this point confused you, there are probably others who are confused - what do you think is the best way to avoid this naming mixup in the future? Deco 05:21, 20 August 2005 (UTC)[reply]

I see - sorry for my confusion. Looking at a couple of other websites (eg. www.complexityzoo.com) it seems that most people use "RL" to describe what you call "RLP". So I might suggest switching to this terminology, or if not, linking to a different reference that uses the same names for these classes that this article does. A third option would be to specifically point out on this page that "RLP" is not known to be equal to NL.

Agreed (to moving the page). See also the discussion at Lance Fortnow's weblog from Sept 08 2005. Wikipedia shouldn't adopt minority POV naming conventions (even though they are well-intentioned). Arbor 19:43, 11 September 2005 (UTC)[reply]

RL != RLP?

I'm rather confused. I know that for deterministic machines, we have DSPACE(f(n)) \subset DTIME(2^f(n)) because in 2^f(n) steps, we can step through every possible configuration of the tape (since is bounded in size by f(n)). So running any longer than that means entering a previously tape configuration, which is useless.

There are polynomially many configurations of logarithmic space; this is why L \subseteq P. What makes the above argument invalid for randomized time? That is, how could RL take more than polynomial time? --Saforrest 05:27, 29 November 2005 (UTC)[reply]

Apparently I should RTFA. --Saforrest 05:31, 29 November 2005 (UTC)[reply]

That's okay - the article also gives an example of an RL algorithm that takes expected exponential time, the coin-flipping algorithm in the NL=RL proof. Deco 05:34, 29 November 2005 (UTC)[reply]

Requested move

The following is a closed discussion of the proposal. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the proposal was} move Anthony Appleyard (talk) 05:24, 10 May 2009 (UTC)[reply]
As "Rl" is not a word, the dab page for the two letters should be in caps - see WP:DABNAME. Even stronger argument in this case, as lower case "L" looks so like capital "I". PamD (talk) 07:03, 9 May 2009 (UTC)[reply]

Agreed. The most (all?) of the uses listed are initialisms, and therefore the correct capitalization is RL. Jafeluv (talk) 08:46, 9 May 2009 (UTC)[reply]

Support as acronym usage. -- JHunterJ (talk) 12:18, 9 May 2009 (UTC)[reply]

The above discussion is preserved as an archive of the proposal. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

Potential additions

Return Loss

RL may also stand for return loss (see article).

I think that it should be added to this list. — Preceding unsigned comment added by 134.191.232.71 (talk) 08:32, 18 June 2013 (UTC)[reply]

Reduced Level

RL may also stand for reduced level (see article). Is it significant enough to add to the list? --RyanCu (talk) 00:58, 13 April 2018 (UTC)[reply]