Complexidade SL

Origem: Wikipédia, a enciclopédia livre.

Na teoria da complexidade computacional, SL (Logspace Simétrica ou Sym-L) é a classe de complexidade dos problemas de log-espaço redutível a USTCON (não-s-t conectividade), é o problema de determinar se existe um caminho entre dois vértices em um grafo não direcionado, caso contrário, descrito como o problema de determinar se dois vértices estão no mesmo componente conectado. Este problema também é chamado de problema da não-acessibilidade. Embora originalmente descrita em termos de máquinas simétricas de Turing, é equivalente a formulação uma muito complexa, e a definição de redutibilidade é o que é usado na prática.

USTCON é um caso especial de STCON (acessibilidade dirigida), o problema de determinar se um caminho dirigido entre dois vértices em um grafo direcionado existe, que é completa para o NL. USTCON é SL-completa, a maioria dos avanços mostram que o impacto USTCON têm também um impacto SL. Assim, eles são conectados, e discutidos em conjunto.

Em outubro de 2004 Omer Reingold mostrou que SL = L.

Origem[editar | editar código-fonte]

SL foi desenvolvido em 1982 por Lewis e Papadimitriou,[1] que estavam procurando uma classe na qual USTCON pertencia, que até este tempo poderia, na melhor das hipóteses, ser colocado somente na NL, apesar da aparente não requerer não determinismo. Eles definiram o máquina simétrica de Turing, e mostrou que USTCON foi para o SL-completa, e provou que

Onde L é a classe mais conhecida de problemas que podem ser resolvidos por uma máquina de Turing determinística no espaço logarítmico, e NL é a classe de problemas que podem ser resolvidos por máquinas de Turing não deterministas no espaço logarítmico. O resultado da Reingold, discutido mais adiante, mostra que, na verdade, quando limitado a log espaço, a máquina de Turing simétrica é equivalente em energia da máquina de Turing determinística.

Problema da completude[editar | editar código-fonte]

Por definição, USTCON é SL-completa (i.e. todos os problemas em SL podem ser reduzidos a ela, incluindo ele próprio). Muitos outros problemas em SL-completa foram encontrados, a maioria por redução direta ou indiretamente, a partir de USTCON, e um compêndio deles foi feita por Àlvarez e Greenlaw.[2] Muitos são problemas da teoria dos grafos. Alguns dos mais simples e mais importante SL-completa que eles descrevem incluem:

  • USTCON
  • Simulação de máquinas simétricas de Turing: um STM aceitar uma dada entrada em um determinado espaço, dado em unário?
  • Vértice-disjunto de caminhos: há k caminhos entre dois vértices, o compartilhamento de vértices apenas nos pontos finais? (uma generalização da USTCON, o equivalente a perguntar se um grafo é k-edge-ligado)
  • É um gráfico dado um grafo bipartido, ou equivalentemente, ele tem um gráfico de colorir usando 2 cores?
  • Fazer dois não-gráficos de ter o mesmo número de componentes conectados?
  • Faz um gráfico tiver um número par de componentes conectados?
  • Dado um grafo, existe um ciclo contendo uma determinada borda?
  • Fazer o que abrange florestas de dois gráficos de ter o mesmo número de arestas?
  • Dado um gráfico onde todas as suas arestas possuem pesos distintos, é um dado de borda no peso mínimo de abrangência da floresta?
  • Exclusiva ou 2-satisfiability: dada uma fórmula exigindo que xi xor xj segure para um número de pares de variáveis (xi,xj), há uma atribuição de variáveis que torna isso verdade?

O complemento de todos estes problemas estão no SL, uma vez que, como veremos, o SL é fechado sob complement.

A partir do fato de que L = SL, segue-se que muitos mais problemas SL-completo, com respeito a reduções em log-espaço: cada problema em L ou em SL é SL-completa; além disso, mesmo se as reduções são em alguns pequenos classe de L, L-integralidade é equivalente a SL-integralidade. Neste sentido, esta classe tornou-se algo trivial.

Resultados importantes[editar | editar código-fonte]

Não são conhecidos algoritmos clássicos, tais como a pesquisa de profundidade-primeiro e amplitude-a primeira pesquisa que resolve USTCON em tempo e espaço linear. A sua existência, mostrado muito antes de SL foi definido, prova que o SL está contido em P. Também não é difícil mostrar que USTCON, e então SL, é na NL, desde que nós podemos apenas não-determinismo acho que em cada vértice vértice que a próxima visita, a fim de descobrir um caminho, se houver.

A primeira tarefa (não 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 log2 n espaço. Ao contrário de pesquisa de profundidade-primeiro, no entanto, este algoritmo é impraticável para a maioria das aplicações devido a seus potenciais superpolynomial tempo de execução. Uma conseqüência disso é que USTCON, e então SL, é no DSPACE(log2n).[3] (na realidade, o teorema de Savitch dá o resultado mais forte que NL é no DSPACE(log2n).)

Apesar de não existirem (uniforme) determinista espaço melhorias no Savitch do, um algoritmo muito prático probabilística log-espaço foi encontrado em 1979 por Aleliunas et al.: basta iniciar um vértice e de efetuar um passeio aleatório até encontrar o outro (aceitar) ou até |V|3 em que o tempo passou (rejeitar).[4] Falsas rejeições são feitos com uma pequena delimitada probabilidade de que diminui exponencialmente mais o passeio aleatório é a continuação. Isto mostrou que o SL está contido no RLP, a classe de problemas resolvidos em tempo polinomial e logarítmica espaço com probabilística máquinas que rejeitar incorretamente menos de 1/3 do tempo. Substituindo o passeio aleatório por um universal transversal sequência, Aleliunas et al. mostrou também que o SL está contido em L/poly, um não-uniforme classe de complexidade dos problemas resolvidos de forma determinística em logarítmica espaço com o polinômio de aconselhamento.

Em 1989, Borodin et al. fortalecido esse resultado mostra que o complemento de USTCON, determinar se dois vértices são ligados diferentes componentes, é também na RLP.[5] Esta colocado USTCON, e SL, em co-RLP e na interseção da RLP e co-RLP, que é ZPLP, a classe de problemas que têm de log-espaço, o esperado em tempo polinomial, sem erro algoritmos randomizados.

Em 1992, Nisan, Szemerédi, e Wigderson , finalmente, encontrado um novo algoritmo determinístico para resolver USTCON usando apenas o registode 1,5 n espaço.[6] Este foi melhorado um pouco, mas não haveria mais significativos ganhos de até Reingold.

Em 1995, Nissan e Ta-Shma mostrou o resultado surpreendente de que o SL é fechado em complemento, o que na época foi considerado por muitos para ser falsa; isto é, SL = co-SL.[7] Equivalentemente, se um problema pode ser resolvido reduzindo-o a um gráfico e perguntando se dois vértices estão na mesma componente, ele também pode ser resolvido reduzindo-o a um outro gráfico e perguntando se dois vértices são em diferentes componentes. No entanto, Reingold do papel viria a tornar este resultado redundante.

Um dos mais importantes corolários do SL = co-SL é que LSL = SL; isto é, um determinista, log-espaço máquina com um oracle para o SL pode resolver problemas no SL (trivialmente), mas não pode resolver outros problemas. Isto significa que não importa se usamos Turing reducibility ou muitos-um reducibility para mostrar o problema está no SL; eles são equivalentes.

Uma descoberta de outubro de 2004, do papel por Omer Reingold mostrou que USTCON é, na verdade, na L.[8] Desde USTCON é SL-completo, isto implica que SL = L, essencialmente, eliminando a utilidade da consideração do SL como uma classe separada. Algumas semanas mais tarde, estudante de pós-graduação Vladimir Trifonov mostrou que USTCON poderia ser resolvido de maneira determinística utilizando O(log n log log n) o espaço—um resultado mais fraco—como utilizar diferentes técnicas.[9]

Consequências de L = SL[editar | editar código-fonte]

O colapso de L e SL tem uma série de conseqüências importantes. Mais obviamente, todas SL-completa problemas estão agora em L, e pode ser uma actividade assalariada, na concepção determinista de log-espaço e polylogarithmic-espaço de algoritmos. Em particular, temos um novo conjunto de ferramentas para usar em log-espaço para reduções. Agora também é sabido que o problema é em L se e somente se ela é log-espaço redutível a USTCON.

Notas[editar | editar código-fonte]

  1. ↑ Lewis, Harry R.; Papadimitriou, Christos H. (1980), «Symmetric space-bounded computation», Proceedings of the Seventh International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 85, Berlin: Springer, pp. 374–384, MR 589018, doi:10.1007/3-540-10003-2_85 .
  2. ↑ Àlvarez, Carme; Greenlaw, Raymond (2000), «A compendium of problems complete for symmetric logarithmic space», Computational Complexity, 9 (2): 123–145, MR 1809688, doi:10.1007/PL00001603 .
  3. ↑ Savitch, Walter J. (1970), «Relationships between nondeterministic and deterministic tape complexities», Journal of Computer and System Sciences, 4: 177–192, MR 0266702, doi:10.1016/S0022-0000(70)80006-X .
  4. ↑ Aleliunas, Romas; Karp, Richard M.; Lipton, Richard J.; Lovász, László; Rackoff, Charles (1979), «Random walks, universal traversal sequences, and the complexity of maze problems», Proceedings of 20th Annual Symposium on Foundations of Computer Science, New York: IEEE, pp. 218–223, MR 598110, doi:10.1109/SFCS.1979.34 .
  5. ↑ Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzo, Walter L.; Tompa, Martin (1989), «Two applications of inductive counting for complementation problems», SIAM Journal on Computing, 18 (3): 559–578, MR 996836, doi:10.1137/0218038 .
  6. ↑ Nisan, Noam; Szemerédi, Endre; Wigderson, Avi (1992), «Undirected connectivity in O(log1.5n) space», Proceedings of 33rd Annual Symposium on Foundations of Computer Science, pp. 24–29, doi:10.1109/SFCS.1992.267822 .
  7. ↑ Nisan, Noam; Ta-Shma, Amnon (1995), «Symmetric logspace is closed under complement», Chicago Journal of Theoretical Computer Science, Article 1, MR 1345937, Predefinição:ECCC .
  8. ↑ Reingold, Omer (2008), «Undirected connectivity in log-space», Journal of the ACM, 55 (4): 1–24, MR 2445014, doi:10.1145/1391289.1391291 .
  9. ↑ Trifonov, Vladimir (2008), «An O(log n log log n) space algorithm for undirected st-connectivity», SIAM Journal on Computing, 38 (2): 449–483, MR 2411031, doi:10.1137/050642381 .

References[editar | editar código-fonte]

  • C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.
  • Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.
Obtida de "https://pt.wikipedia.org/w/index.php?title=Complexidade_SL&oldid=64516499"