b'\n_START_ARTICLE_\nRL (complexidade)\n_START_PARAGRAPH_\nEspa\xc3\xa7o Logar\xc3\xadtmico Randomizado\xc2\xa0(RL), \xc3\xa0s vezes chamado de RLP (Espa\xc3\xa7o Logar\xc3\xadtmico Randomizado de tempo Polinomial), \xc3\xa9 a classe de complexidade\xc2\xa0de problemas da\xc2\xa0teoria da complexidade computacional\xc2\xa0sol\xc3\xbaveis em\xc2\xa0espa\xc3\xa7o logar\xc3\xadtmico\xc2\xa0e tempo polinomial com m\xc3\xa1quinas de Turing probabil\xc3\xadsticas\xc2\xa0com erro unilateral. \xc3\x89 denominado analogamente a RP, que \xc3\xa9 semelhante, mas n\xc3\xa3o tem restri\xc3\xa7\xc3\xa3o logar\xc3\xadtmica\xc2\xa0de espa\xc3\xa7o._NEWLINE_As m\xc3\xa1quinas de Turing probabil\xc3\xadsticas na defini\xc3\xa7\xc3\xa3o de RL nunca aceitam incorretamente, mas s\xc3\xa3o permitidas de rejeitar incorretamente menos de 1/3 das vezes; isso \xc3\xa9 chamado de erro unilateral. A constante 1/3 \xc3\xa9 arbitr\xc3\xa1ria; qualquer x , com 0 < x < 1 seria o suficiente. Este erro pode reduzido 2 vezes para qualquer polin\xc3\xb4mio p(x) sem utilizar mais do que um tempo polinomial ou espa\xc3\xa7o logar\xc3\xadtmico ao se executar o algoritmo v\xc3\xa1rias vezes._NEWLINE_\xc3\x80s vezes, o nome RL \xc3\xa9 reservado para a classe de problemas sol\xc3\xbaveis por m\xc3\xa1quinas probabil\xc3\xadsticas de espa\xc3\xa7o logar\xc3\xadtmico em tempo\xc2\xa0infinito. No entanto, esta classe pode ser demonstrada como sendo igual a NL utilizando um contador probabil\xc3\xadstico, e por isso \xc3\xa9 geralmente referida como NL em vez disso, o que tamb\xc3\xa9m mostra que\xc2\xa0RL est\xc3\xa1 contida em NL. RL est\xc3\xa1 contida em BPL, que \xc3\xa9 semelhante, mas permite erro bilateral (aceita\xc3\xa7\xc3\xb5es incorretas). RL cont\xc3\xa9m L, problemas sol\xc3\xbaveis por m\xc3\xa1quinas de Turing determin\xc3\xadsticas\xc2\xa0em espa\xc3\xa7o logar\xc3\xadtmico, j\xc3\xa1 que sua defini\xc3\xa7\xc3\xa3o \xc3\xa9 apenas mais geral._NEWLINE_Noam Nisan mostrou, em 1992, o resultado fraco de\xc2\xa0derandomiza\xc3\xa7\xc3\xa3o\xc2\xa0fraca\xc2\xa0de que RL est\xc3\xa1 contida em SC, a classe de problemas sol\xc3\xbaveis em tempo polinomial e espa\xc3\xa7o polilogar\xc3\xadtmico numa m\xc3\xa1quina de Turing determin\xc3\xadstica; em outras palavras, dado um espa\xc3\xa7o\xc2\xa0polilogar\xc3\xadtmico, um m\xc3\xa1quina determin\xc3\xadstica\xc2\xa0pode simular algoritmos\xc2\xa0probabil\xc3\xadsticos em espa\xc3\xa7o\xc2\xa0logar\xc3\xadtmico._NEWLINE_Acredita-se que\xc2\xa0RL \xc3\xa9 igual a L, isto \xc3\xa9, que computa\xc3\xa7\xc3\xa3o de tempo polinomial logspace (espa\xc3\xa7o logar\xc3\xadtmico) pode ser completamente desrandomizada (n\xc3\xa3o-aleat\xc3\xb3ria); as principais evid\xc3\xaancias para isso foram apresentadas por Reingold et al. no ano de 2005. Uma prova disso \xc3\xa9 o santo graal dos esfor\xc3\xa7os no campo de desrandomiza\xc3\xa7\xc3\xa3o incondicional de classes de complexidade. Um passo importante foi a prova de Omer Reingold de que SL \xc3\xa9 igual a L.'