st-connectivity

In informatica, la st-connectivity (o STCON) è il problema decisionale che consiste nel verificare se, dati due vertici $s$ e $t$ di un grafo orientato, $t$ è raggiungibile da $s$.

Complessità

Il problema è stato dimostrato essere in NL, in quanto una macchina di Turing non deterministica può indovinare il vertice successivo del percorso, mantenendo come uniche informazioni memorizzate il vertice corrente e la lunghezza totale del percorso. L'algoritmo termina se il vertice $t$ viene raggiunto, oppure se la lunghezza del percorso supera $N$ (il numero di nodi del grafo).

Il problema complemento della st-connectivity, noto come st-non-connectivity, appartiene anch'esso alla classe NL in quanto, per il teorema di Immerman–Szelepcsényi, sappiamo che co-NL=NL.

In particolare, la st-connectivity è un problema NL-completo, ovvero, ogni problema appartenente alla classe NL è riducibile a questo tramite una riduzione in spazio logaritmico. Ciò rimane vero anche nel caso di riduzioni del primo ordine. La riduzione in spazio logaritmico da qualsiasi linguaggio in NL a STCON può essere fatta come segue. Sia $M$ una macchina di Turing non deterministica avente spazio logaritmico che accetta un linguaggio in NL. Dato che il nastro di lavoro della macchina possiede uno spazio logaritmico, allora i possibili stati della macchina di Turing (ovvero: lo stato dell'automa a stati finiti interno, la posizione della testa e il contenuto del nastro di lavoro) sono al più polinomiali. A questo punto, si mappino tutti i possibili stati della macchina deterministica verso i vertici del grafo e si aggiunga un arco tra tutti i vertici $u$ e $v$ se lo stato relativo a $v$ può essere raggiunto da $u$ tramite un passo della macchina non deterministica. Ora, il problema di controllare se la macchina è accettante equivale al problema di verificare se esiste un percorso dallo stato di partenza a quello accettante.

Il teorema di Savitch garantisce che l'algoritmo può essere simulato in uno spazio deterministico $O(log^{2}(n))$.

Lo stesso problema per grafi non orientati viene chiamato undirected s-t connectivity ed è stato dimostrato essere L-completo da Omer Reingold. Questa ricerca portò l'autore a vincere il Grace Murray Hopper Award nel 2005. In origine, il problema di undirected s-t connectivity era noto essere completo per la classe SL, quindi il lavoro di Reingold dimostrò che le classi SL e L coincidono.

Bibliografia

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