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

R é igual ao conjunto de todas as funções computáveis totais.

Relação com outras classes

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

• 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

A Complexidade Do Zoo: Classe R