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.
La classe R és igual a RE ∩ coRE.
Referències
Categoria:Complexitat computacional