R (complexidade)
Na teoria da complexidade computacional, R é a classe de problemas de decisão solúveis por uma máquina de Turing, que é o conjunto de todas as linguagens recursivas.
Formulações equivalentes
[editar | editar código-fonte]R é igual ao conjunto de todas as funções computáveis totais.
Relação com outras classes
[editar | editar código-fonte]Já que podemos decidir qualquer problema para o qual existe um reconhecedor e também um co-reconhecedor por simplesmente intercalá-los até que um obtenha resultado, a classe é igual a RE ∩ coRE.
Referências
[editar | editar código-fonte]- Blum, Lenore, Mike Shub, e Steve Smale. "Em uma teoria da computação e complexidade nos números reais: NP-completude, funções recursivas e máquinas universais." Boletim (Nova Série), da American Mathematical Society 21.1 (1989): 1-46.
Ligações externas
[editar | editar código-fonte]A Complexidade Do Zoo: Classe R