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

  1. ↑ 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.
  2. ↑ «Complexity Zoo:R - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-07-21. [Consulta: 30 novembre 2018].