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