R (složenost)

U računarskoj teoriji složenosti R je klasa problema odlučivosti, koje rešava Tjuringova mašina, a predstavlja skup rekurzivnih jezika.

Ekvivalentne formulacije

R je jednaka skupu svih potpuno izračunljivih funkcija (computable functions).

Relacije prema drugim klasama

Pošto možemo da odlučimo bilo koji problem za koji postoji prepoznavanje i prihvat ulaza i ko-prepoznavanje jednostavnim preklapanjem (interleaving) dok se ne dobije rezultat, klasa je jednaka RE ∩ coRE.

Literatura

• Blum, Lenore, Majk Šab, i Stiv Smejl. "Teorija računanja i složenost realnih brojeva: NP-potpunost, rekurzivne funkcije i univerzalne mašine."