R (clase de complejidad)
En complejidad computacional, R es la clase conformada por los problemas de decisión resolubles por una máquina de Turing, vale decir, el conjunto de todos los lenguajes recursivos. R es usualmente identificado con la clase de funciones efectivamente computables, según la Tesis de Church-Turing.[1]
Esta clase es equivalente a RE ∩ coRE.
Referencias
- Blum, Lenore, Mike Shub, & Steve Smale. (1989). «On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines». Bulletin (New Series) of the American Mathematical Society 21 (1): 1-46.
Enlaces externos
- Complexity Zoo: clase R
| Control de autoridades |
|
|---|
Datos: Q1063293
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.