st-connectivity

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

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 ${\displaystyle t}$ viene raggiunto, oppure se la lunghezza del percorso supera ${\displaystyle 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.^[1] La riduzione in spazio logaritmico da qualsiasi linguaggio in NL a STCON può essere fatta come segue. Sia ${\displaystyle 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 ${\displaystyle u}$ e ${\displaystyle v}$ se lo stato relativo a ${\displaystyle v}$ può essere raggiunto da ${\displaystyle 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 ${\displaystyle 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.

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

Portale Informatica

Portale Matematica