RL (Complexitat)
En teoria de la complexitat, la classe de complexitat RL (també coneguda per RLP) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en espai logarítmic i temps polinòmic. És anàloga a la classe RP, que no té la restricció d'espai logarítmic.[1][2]
La màquina de Turing probabilística de la definició mai accepta incorrectament una entrada, però pot rebutjar incorrectament amb una probabilitat menor de 1/3 (aquesta característica s'anomena error d'una banda (one side error)). La constant 1/3 és arbitrària, qualsevol valor entre 0 i 1 és vàlid.
Relació amb d'altres classes
[modifica]La relació d'aquesta classe amb la classe L és la mateixa que te la classe RP amb a P.[1]
De fet, es creu fermament que RL és equivalent a L. Una troballa significativa en aquest cap va ser la demostració de Omer Reingold de que la classe SL és igual a L. Se sap també que està continguda dins de la classe SC.
Referències
[modifica]- ↑ 1,0 1,1 «Complexity Zoo:R - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-07-21. [Consulta: 1r desembre 2018].
- ↑ Borodin, A.; Cook, S.A.; Dymond, P.W.; Ruzzo, W.L.; Tompa, M. «Two applications of complementation via inductive counting» (en anglès). Proceedings. Structure in Complexity Theory Third Annual Conference. IEEE, 1988. DOI: 10.1109/sct.1988.5271.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
