RL (complexidade)
Espaço Logarítmico Randomizado (RL),[1] às vezes chamado de RLP (Espaço Logarítmico Randomizado de tempo Polinomial),[2] é a classe de complexidade de problemas da teoria da complexidade computacional solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro unilateral. É denominado analogamente a RP, que é semelhante, mas não tem restrição logarítmica de espaço.
As máquinas de Turing probabilísticas na definição de RL nunca aceitam incorretamente, mas são permitidas de rejeitar incorretamente menos de 1/3 das vezes; isso é chamado de erro unilateral. A constante 1/3 é arbitrária; qualquer x , com 0 < x < 1 seria o suficiente. Este erro pode reduzido 2−p(x) vezes para qualquer polinômio p(x) sem utilizar mais do que um tempo polinomial ou espaço logarítmico ao se executar o algoritmo várias vezes.
Às vezes, o nome RL é reservado para a classe de problemas solúveis por máquinas probabilísticas de espaço logarítmico em tempo infinito. No entanto, esta classe pode ser demonstrada como sendo igual a NL utilizando um contador probabilístico, e por isso é geralmente referida como NL em vez disso, o que também mostra que RL está contida em NL. RL está contida em BPL, que é semelhante, mas permite erro bilateral (aceitações incorretas). RL contém L, problemas solúveis por máquinas de Turing determinísticas em espaço logarítmico, já que sua definição é apenas mais geral.
Noam Nisan mostrou, em 1992, o resultado fraco de derandomização fraca de que RL está contida em SC,[3] a classe de problemas solúveis em tempo polinomial e espaço polilogarítmico numa máquina de Turing determinística; em outras palavras, dado um espaço polilogarítmico, um máquina determinística pode simular algoritmos probabilísticos em espaço logarítmico.
Acredita-se que RL é igual a L, isto é, que computação de tempo polinomial logspace (espaço logarítmico) pode ser completamente desrandomizada (não-aleatória); as principais evidências para isso foram apresentadas por Reingold et al. no ano de 2005.[4] Uma prova disso é o santo graal dos esforços no campo de desrandomização incondicional de classes de complexidade. Um passo importante foi a prova de Omer Reingold de que SL é igual a L.
Referências
- ↑ Complexity Zoo: RL
- ↑ A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa.
- ↑ Nisan, Noam (1992), «RL ⊆ SC», Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92), Victoria, British Columbia, Canada, pp. 619–623, doi:10.1145/129712.129772.
- ↑ O. Reingold and L. Trevisan and S. Vadhan.