SL (complexidade) - SL (complexity)

Na teoria da complexidade computacional , SL ( Symmetric Logspace ou Sym-L ) é a classe de complexidade dos problemas de log-espaço redutível a USTCON ( conectividade st não direcionada ), que é o problema de determinar se existe um caminho entre dois vértices em um grafo não direcionado , descrito de outra forma como o problema de determinar se dois vértices estão no mesmo componente conectado . Esse problema também é chamado de problema de acessibilidade não direcionada . Não importa se a redutibilidade muitos-um ou a redutibilidade de Turing é usada. Embora originalmente descrita em termos de máquinas de Turing simétricas , essa formulação equivalente é muito complexa, e a definição de redutibilidade é a que é usada na prática.

USTCON é um caso especial de STCON ( acessibilidade direcionada ), o problema de determinar se existe um caminho direcionado entre dois vértices em um grafo direcionado , que é completo para NL . Como o USTCON está completo com o SL , a maioria dos avanços que afetam o USTCON também afetaram o SL . Assim, eles estão conectados e discutidos juntos.

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

Origem

O SL foi definido pela primeira vez em 1982 por Harry R. Lewis e Christos Papadimitriou , que buscavam uma aula para colocar o USTCON, que até então poderia, na melhor das hipóteses, ser colocado apenas em NL , apesar de parecer não exigir o não-determinismo. Eles definiram a máquina de Turing simétrica , usaram-na para definir SL, mostraram que USTCON era completo para SL e provaram que

${\ displaystyle {\ mathsf {L}} \ subseteq {\ mathsf {SL}} \ subseteq {\ mathsf {NL}}}$

onde L é a classe mais conhecida de problemas solucionáveis ​​por uma máquina de Turing determinística comum no espaço logarítmico e NL é a classe de problemas solucionáveis ​​por máquinas de Turing não determinísticas no espaço logarítmico. O resultado de Reingold, discutido mais tarde, mostra que, de fato, quando limitada ao espaço das toras, a máquina de Turing simétrica é equivalente em potência à máquina de Turing determinística.

Problemas completos

Por definição, USTCON é completo para SL (todos os problemas no SL se reduzem a ele, incluindo ele mesmo). Muitos problemas completos mais interessantes foram encontrados, a maioria reduzindo direta ou indiretamente do USTCON, e um compêndio deles foi feito por Àlvarez e Greenlaw. Muitos dos problemas são problemas de teoria de grafos em grafos não direcionados. Alguns dos problemas SL-completos mais simples e importantes que eles descrevem incluem:

• USTCON
• Simulação de máquinas de Turing simétricas: um STM aceita um dado input em um determinado espaço, dado em unário?
• Caminhos de vértices disjuntos: existem k caminhos entre dois vértices, compartilhando vértices apenas nas extremidades? (uma generalização de USTCON, equivalente a perguntar se um gráfico está conectado por k )
• Um dado gráfico é um gráfico bipartido ou, de forma equivalente, ele tem uma coloração de gráfico usando 2 cores?
• Dois gráficos não direcionados têm o mesmo número de componentes conectados ?
• Um gráfico tem um número par de componentes conectados?
• Dado um gráfico, existe um ciclo contendo uma determinada aresta?
• As florestas abrangentes de dois gráficos têm o mesmo número de arestas?
• Dado um gráfico em que todas as suas arestas têm pesos distintos, uma determinada aresta no peso mínimo abrange a floresta ?
• Exclusivo ou 2 satisfiability : dada uma fórmula que exige que ou espera por um número de pares de variáveis , há uma atribuição para as variáveis que torna verdade?${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle (x_ {i}, x_ {j})}$

Os complementos de todos esses problemas também estão no SL, pois, como veremos, o SL está fechado em complemento.

Do fato de que L = SL , segue-se que muitos mais problemas são SL-completos com respeito às reduções de espaço de log: todo problema não trivial em L ou em SL é SL- completo; além disso, mesmo que as reduções sejam em alguma classe menor do que L , L -completude é equivalente a SL -completude. Nesse sentido, essa aula se tornou um tanto trivial.

Resultados importantes

Existem conhecidos algoritmos clássicos, como busca em profundidade e de procura em largura que resolvem USTCON em tempo linear e do espaço. A sua existência, mostrado muito antes SL foi definido, prova que SL é contido em P . Também não é difícil mostrar que USTCON, e portanto SL , está em NL , uma vez que podemos apenas adivinhar de forma não determinística em cada vértice qual vértice visitar em seguida para descobrir um caminho, se houver.

O primeiro resultado não trivial para SL , entretanto, foi o teorema de Savitch , provado em 1970, que forneceu um algoritmo que resolve USTCON no espaço log ² n . Ao contrário da pesquisa em profundidade, no entanto, esse algoritmo é impraticável para a maioria das aplicações devido ao seu tempo de execução potencialmente superpolinomial. Uma consequência disso é que USTCON, e portanto SL , está em DSPACE (log ² n ) . (Na verdade, o teorema de Savitch dá o resultado mais forte que NL está em DSPACE (log ² n ) .)

Embora não tenha havido melhorias espaciais determinísticas (uniformes) no algoritmo de Savitch por 22 anos, um algoritmo de espaço logístico probabilístico altamente prático foi encontrado em 1979 por Aleliunas et al .: simplesmente comece em um vértice e execute um passeio aleatório até encontrar o outro um (então aceite) ou até | V | ³ tempo se passou (então rejeite). Falsas rejeições são feitas com uma pequena probabilidade limitada que diminui exponencialmente quanto mais tempo o passeio aleatório é continuado. Isso mostrou que o SL está contido no RLP , a classe de problemas solucionáveis ​​em tempo polinomial e espaço logarítmico com máquinas probabilísticas que rejeitam incorretamente menos de 1/3 do tempo. Ao substituir o passeio aleatório por uma sequência de travessia universal, Aleliunas et al. também mostrou que SL está contido em L / poli , uma classe de complexidade não uniforme dos problemas solucionáveis ​​deterministicamente em espaço logarítmico com conselho polinomial .

Em 1989, Borodin et al. reforçou esse resultado ao mostrar que o complemento do USTCON, determinando se dois vértices estão em diferentes componentes conectados, também está no RLP . Isso colocou USTCON, e SL , em co- RLP e na interseção de RLP e co- RLP , que é ZPLP , a classe de problemas que têm algoritmos randomizados de espaço log, tempo polinomial esperado e sem erro.

Em 1992, Nisan , Szemerédi e Wigderson finalmente encontraram um novo algoritmo determinístico para resolver USTCON usando apenas log ^1,5 n espaço. Isso foi ligeiramente melhorado, mas não haveria ganhos mais significativos até Reingold.

Em 1995, Nisan e Ta-Shma mostraram o resultado surpreendente de que o SL é fechado sob complemento, o que na época era considerado por muitos como falso; isto é, SL = co- SL . Da mesma forma, se um problema pode ser resolvido reduzindo-o a um gráfico e perguntando se dois vértices estão no mesmo componente, também pode ser resolvido reduzindo-o a outro gráfico e perguntando se dois vértices estão em componentes diferentes . No entanto, o artigo de Reingold mais tarde tornaria esse resultado redundante.

Um dos corolários mais importantes de SL = co- SL é que L ^SL = SL ; ou seja, uma máquina determinística de espaço logarítmico com um oráculo para SL pode resolver problemas no SL (trivialmente), mas não pode resolver quaisquer outros problemas. Isso significa que não importa se usamos a redutibilidade de Turing ou a redutibilidade muitos-um para mostrar que um problema está no SL ; eles são equivalentes.

Um avanço outubro 2004 papel por Omer Reingold mostrou que USTCON é, de fato, em L . Uma vez que USTCON é SL- completo, isso implica que SL = L , essencialmente eliminando a utilidade de considerar SL como uma classe separada. Algumas semanas depois, o estudante de graduação Vladimir Trifonov mostrou que o USTCON poderia ser resolvido de forma determinística usando o espaço - um resultado mais fraco - usando diferentes técnicas. Não houve um esforço substancial para transformar o algoritmo de Reingold para USTCON em uma formulação prática. Está explícito em seu artigo (e nos que o conduziram) que eles se preocupam principalmente com os assintóticos; como resultado, o algoritmo que ele descreve realmente consumiria memória e tempo. Isso significa que, mesmo para , o algoritmo exigiria mais memória do que a contida em todos os computadores do mundo (um quiloexaexaexabyte). ${\ displaystyle O {\ text {(log}} n {\ text {log log}} n)}$${\ displaystyle 64 ^ {32} \, \ log N}$${\ displaystyle O (N ^ {64 ^ {32}})}$${\ displaystyle N = 2}$

Consequências de L = SL

O colapso de L e SL tem uma série de consequências significativas. Mais obviamente, todos os problemas completos de SL estão agora em L e podem ser empregados com ganho no projeto de algoritmos de espaço logarítmico determinístico e de espaço polilogarítmico. Em particular, temos um novo conjunto de ferramentas para usar em reduções de espaço de log . Também se sabe agora que um problema está em L se e somente se o espaço de log for redutível a USTCON.

Notas de rodapé

Referências

• C. Papadimitriou . Complexidade computacional . Addison-Wesley, 1994. ISBN  0-201-53082-1 .
• Michael Sipser . Introdução à Teoria da Computação . PWS Publishing Co., Boston 1997 ISBN  0-534-94728-X .