Quelles sont les entraves à l'extension de

La preuve d'Omer Reingold que donne un algorithme pour USTCON (dans un graphe orienté U avec des sommets spéciaux et , sont-ils Con $L=SL$ $s$ $t$ CONNECTE?) En utilisant uniquement logspace. L'idée de base est de construire un graphe d'extension à partir du graphe d'origine, puis de faire le tour du graphe d'extension. Le graphique de l'expandeur est créé en quadrillant le graphique d'origine de façon logarithmique plusieurs fois. Dans le graphique de l'expandeur, le diamètre est uniquement logarithmique, donc une recherche DFS de la profondeur logarithmique suffit.

L'extension du résultat à impliquerait l'existence d'un algorithme d'espace de journalisation pour DSTCON - le même, mais pour les graphes orientés D. (Parfois juste STCON.) Ma question, peut-être légèrement douce, est quels sont les principaux obstacles à l'extension de la preuve de Reingold à cela? $L=NL$

On dirait un peu qu'il devrait y avoir une sorte de graphique "expander dirigé". Un type de construction similaire, où vous ajoutez des arêtes correspondant à des chemins dirigés de longueur moyenne, puis des arêtes correspondant à de longues; puis vous pouvez parcourir le graphique avec une profondeur logarithmique en vous déplaçant sur des chemins courts pour arriver à un long; puis revenez à des chemins courts à la fin.

Y a-t-il un défaut majeur dans ce concept? Ou est-ce qu'il n'y a pas de bonnes constructions de tels expanseurs? Ou faut-il en quelque sorte plus de mémoire que la version non dirigée?

Je ne trouve malheureusement pas grand-chose du tout sur les graphiques d'extensions dirigées. En fait, tout ce que j'ai pu trouver était essentiellement /math/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (qui est sans réponse) et https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Y a-t-il un terme différent que je devrais rechercher?

graph-algorithms nondeterminism expanders logspace Alex Meiburg
la source

L = S L

$L=SL$

L = R L

$L=RL$

Voir le point 3. ici . Vous pouvez objecter qu'il s'agit d'une spéculation complète, mais notez que la réponse de Scott fait essentiellement le même point à propos de l'exploration aléatoire des graphiques dirigés.

Thomas Klimpel

$n$ $t$ $s$ $s$ $t$ $2^n$ $USTCON$ $RL=NL$ $L=NL$ $O(\log^2 n)$

Scott Aaronson
la source

Le type d'algorithme que je décrirais serait, en gros - eh bien, vous exécutez l'opération "carré et zigzag" de Reingold plusieurs fois pour commencer. Je suppose que la modification serait qu'au lieu du carré ne contenant que des chemins de longueur 2 dans le graphique d'origine, il inclut des chemins de longueur 1 et 2. Essayez toutes les séquences logarithmiquement profondes, comme la sienne. Si nous numérotons les sommets de votre graphique comme 1, 2, .. n, alors le premier graphique «carré» relie 1 à 2 et 3, le «carré» suivant le relie à 2345, etc. Les pas en zig-zag gardent les degrés faible. Évidemment rude, mais je ne vois pas pourquoi cela échoue.

Alex Meiburg

\frac{n}{2^{Θ (\sqrt{\log n})}}

$\frac{n}{2^{\Theta(\sqrt{\log n})}}$

\frac{n}{2^{Θ (\sqrt{\log n})}}

$\frac{n}{2^{\Theta(\sqrt{\log n})}}$

\log n

$\log n$

Quelles sont les entraves à l'extension de

Réponses: