R (složitost) - R (complexity) - Wikipedia
v teorie výpočetní složitosti, R je třída rozhodovací problémy řešitelný a Turingův stroj, což je množina všech rekurzivní jazyky.
Ekvivalentní formulace
R se rovná množině všech součtů vypočítatelné funkce.
Vztah s ostatními třídami
Protože můžeme rozhodnout o jakémkoli problému, pro který existuje a rozpoznávač a také společný rozpoznávač jednoduchým prokládáním, dokud jeden nezíská výsledek, třída se rovná RE ∩ co-RE.
Reference
- Blum, Lenore, Mike Shub a Steve Smale. „K teorii výpočtu a složitosti reálných čísel: NP-úplnost, rekurzivní funkce a univerzální stroje.“ Bulletin (New Series) of the American Mathematical Society 21.1 (1989): 1-46.
externí odkazy
| P ≟ NP | Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |