![]() | Disambiguation | |||
|
RL = NL?
editThis 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)
- 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)
RL != RLP?
editI'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)
- Apparently I should RTFA. --Saforrest 05:31, 29 November 2005 (UTC)
- 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)
Requested move
edit- 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)
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)
- 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)
- Support as acronym usage. -- JHunterJ (talk) 12:18, 9 May 2009 (UTC)
- 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
editReturn Loss
editRL 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)
Reduced Level
editRL 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)