Worldlex Wiki
Article de reference

connectivité st

En informatique , la connectivité st ou STCON est un problème de décision qui demande, pour les sommets s et t dans un graphe orienté , si t est accessible depuis s . Formelleme...

Worldlex WikiFrancaisLecture gratuite

En informatique , la connectivité st ou STCON est un problème de décision qui demande, pour les sommets s et t dans un graphe orienté , si t est accessible depuis s .

Formellement, le problème de décision est donné par

D , s , t ⟩ | D est un graphe orienté avec un chemin du sommet s au sommet t } .

Complexité

Sur un ordinateur séquentiel, le problème de la st-connectivité se résout aisément en temps linéaire par un parcours en profondeur ou en largeur . L'intérêt de ce problème en complexité algorithmique réside dans sa complexité par rapport à des formes de calcul plus limitées. Par exemple, la classe de complexité des problèmes résolubles par une machine de Turing non déterministe avec une quantité de mémoire logarithmique est appelée NL . On peut démontrer que le problème de la st-connectivité appartient à NL, car une machine de Turing non déterministe peut prédire le nœud suivant du chemin, les seules informations à stocker étant la longueur totale du chemin et le nœud considéré. L'algorithme s'arrête soit lorsque le nœud cible t est atteint, soit lorsque la longueur du chemin parcouru dépasse n , le nombre de nœuds du graphe.

Le complément de la st-connectivité , connu sous le nom de st-non-connectivité , est également dans la classe NL, puisque NL = coNL par le théorème d'Immerman–Szelepcsényi .

In particular, the problem of st-connectivity is actually NL-complete, that is, every problem in the class NL is reducible to connectivity under a log-space reduction. This remains true for the stronger case of first-order reductions51). The log-space reduction from any language in NL to STCON proceeds as follows: Consider the non-deterministic log-space Turing machine M that accepts a language in NL. Since there is only logarithmic space on the work tape, all possible states of the Turing machine (where a state is the state of the internal finite state machine, the position of the head and the contents of the work tape) are polynomially many. Map all possible states of the deterministic log-space machine to vertices of a graph, and put an edge between u and v if the state v can be reached from u within one step of the non-deterministic machine. Now the problem of whether the machine accepts is the same as the problem of whether there exists a path from the start state to the accepting state.

Savitch's theorem guarantees that the algorithm can be simulated in O(log2n) deterministic space.

The same problem for undirected graphs is called undirected s-t connectivity and was shown to be in L by Omer Reingold. This research won him the 2005 Grace Murray Hopper Award. Undirected st-connectivity was previously known to be complete for the class SL, so Reingold's work showed that SL is the same class asL. On alternating graphs, the problem is P-complete 54).