Какие препятствия для расширения

Доказательство Омер Рейнгольда , что дает алгоритм USTCON (В U ndirected граф со специальными вершинами S и т , они Con подсоединены?) , Используя только logspace. Основная идея состоит в том, чтобы построить график расширителя из исходного графика, а затем выполнить обход в графике расширителя. График экспандера составляется путем возведения в квадрат исходного графика логарифмически много раз. На графике расширителя диаметр является только логарифмическим, поэтому достаточно выполнить поиск по логарифмической глубине в DFS.$L=SL$$s$$t$

Расширение результата до подразумевало бы существование алгоритма логического пространства для DSTCON - то же самое, но для D- ориентированных графов. (Иногда просто STCON.) Мой вопрос, может быть, немного мягкий, каковы основные препятствия для распространения доказательства Рейнгольда на это?$L=NL$

Чувствуется, что должен быть своего рода график «направленного экспандера». Аналогичная конструкция, в которой вы добавляете ребра, соответствующие направленным путям средней длины, а затем некоторые, соответствующие длинным; и затем вы можете перемещаться по графику с логарифмической глубиной, перемещаясь по коротким путям, чтобы добраться до длинных; затем вернемся к коротким путям в конце.

Есть ли главный недостаток в этой концепции? Или нет хороших конструкций таких расширителей? Или это как-то требует больше памяти, чем ненаправленная версия?

Я, к сожалению, не могу найти много на графиках направленного расширителя. Фактически все, что я мог найти, было /math/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (что остается без ответа) и https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Есть ли другой термин, под которым я должен искать?

Центральная проблема заключается в том, что на ориентированных графах даже действительно случайное блуждание не попадает во все вершины в ожидаемое полиномиальное время, не говоря уже о псевдослучайном блуждании. Стандартный контрпример здесь представляет собой ориентированный граф с вершинами, упорядоченными слева направо, где каждая вершина имеет ребро, ведущее к вершине справа (за исключением самой правой вершины t ), и каждая вершина также имеет ребро, ведущее все обратный путь к самой левой вершине, с . Чтобы добраться от s до t случайным блужданием, нужно ~ 2 n времени. Итак, что же представляет собой рандомизированный алгоритм малого пространства для направленной связи, который мы надеемся дерандомизировать, аналогично тому, что сделал Рейнгольд для$n$$t$$s$$s$$t$$2^n$ ? (Другими словами, как мы показываем R L = N L , не говоря уже о L = N L ?). Для направленной связности, конечно, есть алгоритм Савича, но для этого требуетсяпространство O ( log 2 n ) , а для общих графов никому не удавалось улучшить его за полвека, с использованием случайности или без нее.$USTCON$$RL=NL$$L=NL$$O(\log^2 n)$