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

19

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

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

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

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

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


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

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

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

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

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

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


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

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

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

Андраш Саламон
источник
Ваш вывод ", так что, по крайней мере ... требуется пространство для UStCONN", не следует из остальной части его предложения, поскольку в для которых такого δ не существует.o(log(log(n)))δ
5
Входное представление становится важным, так как с пробелом мы не можем указать или получить доступ к произвольному расположению на входе. Какое входное представление вы используете? Можем ли мы показать, что USTCONN находится в недетерминированном сублогарифмическом пространстве? o(logn)
Томас поддерживает Монику
FO = LTH = DLogTime равномерное AC ^ 0
Kaveh
это очень подробно, и это здорово, но, похоже, это поможет связать это с «официально известными / признанными открытыми проблемами», а также с известными полными проблемами (см. некоторые из последних, но, может быть, более подробно?) ... из которых, по-видимому, довольно близко ... и обратите внимание, что se не является хорошим форматом для этого, если это так ... кстати, U в USTConn, кажется, выступает за Ненаправленный, верно? К вашему сведению, SJ на этом сайте изучил нижние границы STConn «низкого уровня» и его взаимосвязь с USTConn, ofc, кажется, будут очень естественные связи
vzn
Возможно, может помочь метод сложности связи для доказательства нижней границы пространства времени: если пространство меньше, чем тогда время меньше, чем n 2, поэтому пространство времени меньше, чем n 2 log n . Можем ли мы как-то избавиться от журнала n в пространстве-времени и показать, что если пространство меньше log n, то пространство-время меньше n 2 ? lognn2n2lognlognlognn2
Каве

Ответы:

13

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

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

SamiD
источник
1
Благодарность! Это, кажется, развитие моего последнего комментария о L-полноте USTCONN. Однако, мне не ясно, что сокращение от ORD может быть сделано в сублогарифмическом пространстве, так что это, кажется, не отвечает на главный вопрос, показывающий, что USTCONN действительно требует по крайней мере логарифмического пространства. Что мне не хватает?
Андрас Саламон
1
@AndrasSalamon: Вам не хватает вопроса Томаса о представлении входных данных, даже если он не отвечает на вопрос, который вы только что задали.