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.
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.
