b'\n_START_ARTICLE_\nComplexidade SL\n_START_PARAGRAPH_\nNa teoria da complexidade computacional, SL (Logspace\xc2\xa0Sim\xc3\xa9trica ou Sym-L) \xc3\xa9 a classe de complexidade dos problemas de log-espa\xc3\xa7o redut\xc3\xadvel a USTCON (n\xc3\xa3o-s-t conectividade), \xc3\xa9 o problema de determinar se existe um caminho entre dois v\xc3\xa9rtices em um grafo n\xc3\xa3o direcionado, caso contr\xc3\xa1rio, descrito como o problema de determinar se dois v\xc3\xa9rtices est\xc3\xa3o no mesmo\xc2\xa0componente conectado. Este problema tamb\xc3\xa9m \xc3\xa9 chamado de problema da n\xc3\xa3o-acessibilidade. Embora originalmente descrita em termos de m\xc3\xa1quinas sim\xc3\xa9tricas de Turing, \xc3\xa9 equivalente a formula\xc3\xa7\xc3\xa3o uma muito complexa, e a defini\xc3\xa7\xc3\xa3o de redutibilidade \xc3\xa9 o que \xc3\xa9 usado na pr\xc3\xa1tica._NEWLINE_USTCON \xc3\xa9 um caso especial de STCON (acessibilidade\xc2\xa0dirigida), o problema de determinar se um caminho dirigido\xc2\xa0entre dois v\xc3\xa9rtices em um grafo direcionado existe, que \xc3\xa9 completa para o NL. USTCON \xc3\xa9 SL-completa, a maioria dos avan\xc3\xa7os mostram que o impacto USTCON t\xc3\xaam tamb\xc3\xa9m um impacto SL. Assim, eles s\xc3\xa3o conectados, e discutidos em conjunto._NEWLINE_Em outubro de 2004 Omer Reingold mostrou que SL = L.\n_START_SECTION_\nOrigem\n_START_PARAGRAPH_\nSL foi desenvolvido em 1982 por Lewis e Papadimitriou, que estavam procurando uma classe na qual USTCON pertencia, que at\xc3\xa9 este tempo poderia, na melhor das hip\xc3\xb3teses, ser colocado somente na NL, apesar da aparente n\xc3\xa3o requerer n\xc3\xa3o determinismo. Eles definiram o m\xc3\xa1quina sim\xc3\xa9trica de Turing, e mostrou que USTCON foi para o SL-completa, e provou que_NEWLINE_Onde L \xc3\xa9 a classe mais conhecida de problemas que podem ser resolvidos por uma m\xc3\xa1quina de Turing determin\xc3\xadstica no espa\xc3\xa7o logar\xc3\xadtmico, e NL \xc3\xa9 a classe de problemas que podem ser resolvidos por m\xc3\xa1quinas de Turing n\xc3\xa3o deterministas no espa\xc3\xa7o logar\xc3\xadtmico. O resultado da Reingold, discutido mais adiante, mostra que, na verdade, quando limitado a log espa\xc3\xa7o, a m\xc3\xa1quina de Turing sim\xc3\xa9trica \xc3\xa9 equivalente em energia da m\xc3\xa1quina de Turing determin\xc3\xadstica.\n_START_SECTION_\nResultados importantes\n_START_PARAGRAPH_\nN\xc3\xa3o s\xc3\xa3o conhecidos algoritmos cl\xc3\xa1ssicos, tais como a pesquisa de profundidade-primeiro e amplitude-a primeira pesquisa que resolve USTCON em tempo e espa\xc3\xa7o linear. A sua exist\xc3\xaancia, mostrado muito antes de SL foi definido, prova que o SL est\xc3\xa1 contido em P. Tamb\xc3\xa9m n\xc3\xa3o \xc3\xa9 dif\xc3\xadcil mostrar que USTCON, e ent\xc3\xa3o SL, \xc3\xa9 na NL, desde que n\xc3\xb3s podemos apenas n\xc3\xa3o-determinismo acho que em cada v\xc3\xa9rtice v\xc3\xa9rtice que a pr\xc3\xb3xima visita, a fim de descobrir um caminho, se houver._NEWLINE_A primeira tarefa (n\xc3\xa3o trivial) resultado para o SL, no entanto, foi o teorema de Savitch, revelou-se em 1970, o que proporcionou um algoritmo que resolve USTCON no log\xc2\xb2 n espa\xc3\xa7o. Ao contr\xc3\xa1rio de pesquisa de profundidade-primeiro, no entanto, este algoritmo \xc3\xa9 impratic\xc3\xa1vel para a maioria das aplica\xc3\xa7\xc3\xb5es devido a seus potenciais superpolynomial tempo de execu\xc3\xa7\xc3\xa3o. Uma conseq\xc3\xbc\xc3\xaancia disso \xc3\xa9 que USTCON, e ent\xc3\xa3o SL, \xc3\xa9 no DSPACE(log\xc2\xb2n). (na realidade, o teorema de Savitch d\xc3\xa1 o resultado mais forte que NL \xc3\xa9 no DSPACE(log\xc2\xb2n).)_NEWLINE_Apesar de n\xc3\xa3o existirem (uniforme) determinista espa\xc3\xa7o melhorias no Savitch do, um algoritmo muito pr\xc3\xa1tico probabil\xc3\xadstica log-espa\xc3\xa7o foi encontrado em 1979 por Aleliunas et al.: basta iniciar um v\xc3\xa9rtice e de efetuar um passeio aleat\xc3\xb3rio at\xc3\xa9 encontrar o outro (aceitar) ou at\xc3\xa9 |V|\xc2\xb3 em que o tempo passou (rejeitar). Falsas rejei\xc3\xa7\xc3\xb5es s\xc3\xa3o feitos com uma pequena delimitada probabilidade de que diminui exponencialmente mais o passeio aleat\xc3\xb3rio \xc3\xa9 a continua\xc3\xa7\xc3\xa3o. Isto mostrou que o SL est\xc3\xa1 contido no RLP, a classe de problemas resolvidos em tempo polinomial e logar\xc3\xadtmica espa\xc3\xa7o com probabil\xc3\xadstica m\xc3\xa1quinas que rejeitar incorretamente menos de 1/3 do tempo. Substituindo o passeio aleat\xc3\xb3rio por um universal transversal sequ\xc3\xaancia, Aleliunas et al. mostrou tamb\xc3\xa9m que o SL est\xc3\xa1 contido em L/poly, um n\xc3\xa3o-uniforme classe de complexidade dos problemas resolvidos de forma determin\xc3\xadstica em logar\xc3\xadtmica espa\xc3\xa7o com o polin\xc3\xb4mio de aconselhamento._NEWLINE_Em 1989, Borodin et al. fortalecido esse resultado mostra que o complemento de USTCON, determinar se dois v\xc3\xa9rtices s\xc3\xa3o ligados diferentes componentes, \xc3\xa9 tamb\xc3\xa9m na RLP. Esta colocado USTCON, e SL, em co-RLP e na interse\xc3\xa7\xc3\xa3o da RLP e co-RLP, que \xc3\xa9 ZPLP, a classe de problemas que t\xc3\xaam de log-espa\xc3\xa7o, o esperado em tempo polinomial, sem erro algoritmos randomizados._NEWLINE_Em 1992, Nisan, Szemer\xc3\xa9di, e Wigderson , finalmente, encontrado um novo algoritmo determin\xc3\xadstico para resolver USTCON usando apenas o registode 1,5 n espa\xc3\xa7o. Este foi melhorado um pouco, mas n\xc3\xa3o haveria mais significativos ganhos de at\xc3\xa9 Reingold._NEWLINE_Em 1995, Nissan e Ta-Shma mostrou o resultado surpreendente de que o SL \xc3\xa9 fechado em complemento, o que na \xc3\xa9poca foi considerado por muitos para ser falsa; isto \xc3\xa9, SL = co-SL. Equivalentemente, se um problema pode ser resolvido reduzindo-o a um gr\xc3\xa1fico e perguntando se dois v\xc3\xa9rtices est\xc3\xa3o na mesma componente, ele tamb\xc3\xa9m pode ser resolvido reduzindo-o a um outro gr\xc3\xa1fico e perguntando se dois v\xc3\xa9rtices s\xc3\xa3o em diferentes componentes. No entanto, Reingold do papel viria a tornar este resultado redundante._NEWLINE_Um dos mais importantes corol\xc3\xa1rios do SL = co-SL \xc3\xa9 que LSL = SL; isto \xc3\xa9, um determinista, log-espa\xc3\xa7o m\xc3\xa1quina com um oracle para o SL pode resolver problemas no SL (trivialmente), mas n\xc3\xa3o pode resolver outros problemas. Isto significa que n\xc3\xa3o importa se usamos Turing reducibility ou muitos-um reducibility para mostrar o problema est\xc3\xa1 no SL; eles s\xc3\xa3o equivalentes._NEWLINE_Uma descoberta de outubro de 2004, do papel por Omer Reingold mostrou que USTCON \xc3\xa9, na verdade, na L. Desde USTCON \xc3\xa9 SL-completo, isto implica que SL = L, essencialmente, eliminando a utilidade da considera\xc3\xa7\xc3\xa3o do SL como uma classe separada. Algumas semanas mais tarde, estudante de p\xc3\xb3s-gradua\xc3\xa7\xc3\xa3o Vladimir Trifonov mostrou que USTCON poderia ser resolvido de maneira determin\xc3\xadstica utilizando O(log n log log n) o espa\xc3\xa7o\xe2\x80\x94um resultado mais fraco\xe2\x80\x94como utilizar diferentes t\xc3\xa9cnicas.\n_START_SECTION_\nConsequ\xc3\xaancias de L = SL\n_START_PARAGRAPH_\nO colapso de L e SL tem uma s\xc3\xa9rie de conseq\xc3\xbc\xc3\xaancias importantes. Mais obviamente, todas SL-completa problemas est\xc3\xa3o agora em L, e pode ser uma actividade assalariada, na concep\xc3\xa7\xc3\xa3o determinista de log-espa\xc3\xa7o e polylogarithmic-espa\xc3\xa7o de algoritmos. Em particular, temos um novo conjunto de ferramentas para usar em log-espa\xc3\xa7o para redu\xc3\xa7\xc3\xb5es. Agora tamb\xc3\xa9m \xc3\xa9 sabido que o problema \xc3\xa9 em L se e somente se ela \xc3\xa9 log-espa\xc3\xa7o redut\xc3\xadvel a USTCON.'