Conectividade st

Em ciência da computação e teoria da complexidade computacional, conectividade st é um problema de decisão onde dados os vértices s e t de um grafo direcionado, questiona-se se t é acessível partindo de s.

Formalmente, o problema de decisão é dada por

PATH = {⟨D, s, t⟩ | D é um grafo direcionado com um caminho do vértice s para outro vértice t}.

Complexidade

Pode ser mostrado que o problema pertence a NL, já que uma máquina de turing não-determinística pode adivinhar o próximo nó do caminho, enquanto que a única informação que tem de ser armazenada é a de qual nó é o nó atualmente sob consideração. O algoritmo termina se o nó de destino t é atingido, ou o caminho até o momento excede n, o número de nós no gráfico.

O complemento de conectividade st, conhecido como não conectividade st, também está na classe NL, desde que o teorema NL = coNL foi formulado por [Immerman-Szelepcsényi]].

Em particular, o problema da conectividade st é realmente NL-completo, isto é, todos os problemas na classe NL são redutíveis a conectividade sob uma redução de espaço logarítmico. A redução de espaço log a partir de qualquer linguagem em NL para conectividade st segue da seguinte forma: Considerar a máquina de turing não-determinística M, de espaço log, que aceita uma linguagem em NL. Como só há espaço logarítmico na fita de trabalho, todos os estados possíveis da máquina de Turing (onde o estado é o estado da máquina interna de estado finito, a posição da cabeça e do conteúdo da fita de trabalho) são polinomialmente redutíveis. Mapear todos os estados possíveis da máquina determinística de espaço log a vértices de um grafo, e colocar uma aresta entre u e v se o estado v pode ser alcançado a partir de u através de um passo da máquina não-determinista. Agora, o problema de saber se a máquina aceita uma dada entrada, é o mesmo que o problema de saber se existe um caminho a partir do estado inicial para o estado de aceitação.

O teorema de Savitch garante que o algoritmo pode ser simulado em O(log² n) para espaço determinístico.

O mesmo problema para grafo não direcionado é chamado de conectividade st não-direcionada e está na classe SL sob reduções em espaço log. Em 2005, Omer Reingold ganhou o Prêmio Grace Murray Hopper por descobrir um algoritmo deterministico de espaço log para conectividade st não-direcionada, o que mostra que SL é igual a L.

Referências

• Sipser, Michael (2006), Introduction to the Theory of Computation, ISBN 0-534-95097-3, Thompson Course Technology 
• Immerman, Neil (1999), Descriptive Complexity, ISBN 0-387-98600-6, New York: Springer-Verlag