R (сложеност)
У рачунарској теорији сложености R је класа проблема одлучивости, које решава Тјурингова машина, а представља скуп рекурзивних језика.
Еквивалентне формулације
уредиR је једнака скупу свих потпуно израчунљивих функција (computable functions).
Релације према другим класама
уредиПошто можемо да одлучимо било који проблем за који постоји препознавање и прихват улаза и ко-препознавање једноставним преклапањем (interleaving) док се не добије резултат, класа је једнака RE ∩ coRE.
Литература
уреди- Блум, Леноре, Мајк Шаб, и Стив Смејл. "Теорија рачунања и сложеност реалних бројева: NP-потпуност, рекурзивне функције и универзалне машине."