Пређи на садржај

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

С Википедије, слободне енциклопедије

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

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

[уреди | уреди извор]

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

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

[уреди | уреди извор]

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

Литература

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