В теорії складності обчислень класом R (від англ. the recursive languages) називають безліч всіх рекурсивних мов. Еквівалентно клас R можна визначити як безліч задач розпізнавання (англ.) вирішуваних на машині Тьюринга. Клас R дорівнює перетинанню класів RE і co-RE.


Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP ( co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів