R (Complexitat)
En teoria de la complexitat, la classe de complexitat R és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing, que és el conjunt de tots els llenguatges recursius. Per tant, R equival al conjunt de totes les funcions computables.[1]
La classe R és igual a RE ∩ coRE.[2]
Referències
[modifica]- ↑ Blum, Lenore; Shub, Mike; Smale, Steve «On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines» (en anglès). Bulletin of the American Mathematical Society, 21, 1, 1989, pàg. 1–46. DOI: 10.1090/S0273-0979-1989-15750-9. ISSN: 0273-0979.
- ↑ «Complexity Zoo:R - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-07-21. [Consulta: 30 novembre 2018].
| 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 | |
