St-connectivity
Template:Titolo minuscolo In informatica, la st-connectivity (o STCON) è il problema decisionale che consiste nel verificare se, dati due vertici e di un grafo orientato, è raggiungibile da .
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 viene raggiunto, oppure se la lunghezza del percorso supera (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 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 e se lo stato relativo a può essere raggiunto da 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 .
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.