R (Complexitat)

classe de 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ènciesModifica

  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). [Consulta: 30 novembre 2018].