Как доказать, что USTCONN требует логарифмического пространства?

USTCONN - это проблема, которая требует решения о том, существует ли путь от исходной вершины $s$ до целевой вершины $t$ в графе $G$ , где все они представлены как часть входных данных.

Омер Рейнгольд показал, что USTCONN находится в L (doi: 10.1145 / 1391289.1391291 ). Доказательство создает расширитель постоянной степени с помощью зигзагообразного произведения. Расширитель постоянной степени имеет логарифмический диаметр, и затем можно проверить все возможные пути, используя постоянное число маркеров логарифмического размера.

Результат Рейнгольда дает логарифмическую верхнюю границу пространственной сложности USTCONN, разрешая ее пространственную сложность «с точностью до постоянного множителя» согласно статье. Меня интересует соответствующая нижняя граница, которая нигде в статье не упоминается.

Как можно доказать, что логарифмическое пространство требуется для определения USTCONN в худшем случае?

Редактировать: Исправить, чтобы входное представление было матрицей смежности $N \times N$ базового симметричного простого ориентированного графа с $N$ вершинами, со строками, перечисленными последовательно для формирования $N^2$ -битной строки.

Льюис и Пападимитриу показали (doi: 10.1016 / 0304-3975 (82) 90058-5 ), что USTCONN является SL-полным, что с учетом результата Рейнгольда означает, что SL = L. Савич показал (doi: 10.1016 / S0022-0000 (70) 80006-X ), что $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$ . Далее $\text{DSPACE}(f(n)) = \text{DSPACE}(1)$ для любой вычислимой функции $f(n) = o(\log\log n)$Stearns, Hartmanis и Lewis (doi: 10.1109 / FOCS.1965.11 ), поэтому для USTCONN требуется как минимум пространство $\Omega(\log\log n)$ . Наконец, обычные классы, о которых известно, что они находятся ниже L (например, $\text{NC}^1$ ), определены в терминах цепей и явно не сравнимы с каким-либо классом, определенным в терминах пространственной границы.

Насколько я могу видеть, это оставляет открытой (по общему признанию маловероятной) возможность того, что существует даже лучший детерминированный алгоритм, который использует только пространство но пространство Ω ( log log n ) , для некоторого δ < 1 , или даже недетерминирован алгоритм USTCONN , который использует O ( ( журнал п ) 1 / 2 ) пространство.$O((\log n)^\delta)$$\Omega(\log \log n)$$\delta < 1$$o((\log n)^{1/2})$

По теореме о пространственной иерархии , пока f ( n ) конструируемо в пространстве. Это может показаться, что USTCONN не может быть в DSPACE ( o ( log) н ) $\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$$f(n)$$\text{DSPACE}(o(\log n))$, Однако USTCONN, завершенный для L при сокращениях пространства журналов, похоже, не подразумевает этого. Кажется, все еще возможно, что USTCONN имеет достаточно структуры для кодирования любой проблемы в L посредством сокращения пространства журналов, однако самому USTCONN требуется только сублогарифмическое пространство.

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

Закончен ли USTCONN для L при сокращении, которое требует пробела?$o(\log n)$

Иммерман показал (doi: 10.1137 / 0216051 ), что версия направленной достижимости, в которой требуемый путь (но не сам граф) является детерминированной, является полной для L при редукциях первого порядка, которые вычисляются цепями AC 0 . Затем это может быть, возможно, адаптировано, чтобы показать, что USTCONN завершено для L при FO-сокращениях. Однако, хотя AC 0 строго содержится в L, AC 0 снова является классом схемы, и я не знаю ни одного способа выполнения FO-сокращений в сублогарифмическом пространстве.$^0$$^0$$^0$

Edit 2015-07-14: Это интересный философский вопрос, должно ли использование пространства TM включать размер индекса во вход (что позволяет произвольный доступ к входу, но требует дополнительного бита, если вход удваивается в размере ) или является ли пространство, используемое ТМ, количеством квадратов рабочей ленты, посещенных во время вычисления (что предполагает фиксированную головку входной ленты и не изменяется, когда размер входной ленты удваивается). Прежнее определение в стиле RAM сразу дает нижнюю границу пространства журналов для любоговычисления и моделирует текущие компьютеры, которые отслеживают текущую позицию в файле как смещение от начала файла. Последнее классическое определение предполагает бумажную ленту с фиксированной головкой чтения, которая ничего не знает о ленте, кроме текущего входного символа, что, возможно, и было тем, что Тьюринг намеревался в своей статье 1937 года.

Эвристические аргументы, такие как комментарий Томаса о том, что невозможно даже проиндексировать ввод с битами пространства, по-видимому, предполагают современное определение в стиле RAM. Stearns / Hartmanis / Lewis используют определение в стиле ТМ, как и большинство классических работ в ограниченных пространством вычислениях.$o(\log n)$

Можно доказать нижнюю границу логического пространства для USTCONN, представленную в виде матрицы смежности, отметив, что для распознавания унарного языка совершенных квадратов требуется логическое пространство (см. Rūsiņš Freivalds, Модели вычислений, Гипотеза Римана и Классическая математика , SOFSEM 1998, LNCS 1521, 89). –106. Doi: 10.1007 / 3-540-49477-4_6 ( препринт)). Тогда та же самая нижняя граница применяется к USTCONN с представлением матрицы смежности. Это, пожалуй, слишком большой обман: обычно выполнение обещания в задаче обещания должно быть легким по сравнению с реальной проблемой, но здесь соблюдение обещания, что входные данные являются графиком, уже дает нижнюю границу. Поэтому было бы неплохо увидеть аргумент для нижней границы пространства журнала для задачи обещания, в которой гарантированно вводится язык .$\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$

В статье « Счетные квантификаторы, преемственные отношения и логарифмическое пространство » Коуши Этессами доказано, что задача (которая по существу проверяет, предшествует ли вершина s вершине t в одном графе G , который обещан быть путем), L- жесткий под квантификатором свободных проекций.$\mathbf{ORD}$$s$$t$$G$$\mathsf{L}$

Проблема можно увидеть , чтобы свести к задаче U S Т С О Н Н , с помощью Р О -reductions: Учитывая экземпляр ⟨ G , ев , т ⟩ из O R D просто удалить ребро из т и выход другие ребра у → V , как неориентированных ребер { U , V } U S Т С О Н Н вопрос , является ли$\mathbf{ORD}$$\mathbf{USTCONN}$$\mathsf{FO}$$\langle G,s,t\rangle$$\mathbf{ORD}$$t$$u \rightarrow v$$\{u,v\}$$\mathbf{USTCONN}$ связаны в результирующем графе. (Примечание: сокращение, вероятно, может быть сделано еще лучше.)$s,t$