R (сложеност)

У рачунарској теорији сложености R је класа проблема одлучивости, које решава Тјурингова машина, а представља скуп рекурзивних језика.

Еквивалентне формулације

R је једнака скупу свих потпуно израчунљивих функција (computable functions).

Релације према другим класама

Пошто можемо да одлучимо било који проблем за који постоји препознавање и прихват улаза и ко-препознавање једноставним преклапањем (interleaving) док се не добије резултат, класа је једнака RE ∩ coRE.

Литература

• Блум, Леноре, Мајк Шаб, и Стив Смејл. "Теорија рачунања и сложеност реалних бројева: NP-потпуност, рекурзивне функције и универзалне машине."