R (complexidade)

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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