Есть ли основания полагать, что

22

Интересно, есть ли основания полагать, что или верить, что N L L ?NL=LNLL

Известно, что . Литература по derandomization из R L является довольно убедительным , что R L = L . Кто-нибудь знает о каких-то статьях или идеях, убеждая, что N L L ?NLL2RLRL=LNLL

Клим
источник

Ответы:

30

Во- первых, позвольте мне привести скепсис , что . Поскольку было показано, что связность неориентированного графа есть в L (Рейнгольд), и что N L = c o N L (Immerman-Szelepcsényi), я думаю, что доверие к L N L только уменьшилось. Некоторые выдающиеся исследователи никогда не верили. Например, Юрис Хартманис (основатель отдела CS в лауреате премии Корнелла и Тьюринга) сказал:LNLLNL=coNLLNL

Мы считаем, что NLOGSPACE отличается от LOGSPACE, но не с той же глубиной убежденности, что и для других классов сложности. (Источник)

Я знаю, что он говорил подобные вещи в литературе еще в 70-х годах.

Есть некоторые доказательства против , хотя это косвенно. Была проведена работа по доказательству нижних границ пространства для s - t- связности (канонической N L -полной задачи) в ограниченных вычислительных моделях. Эти модели достаточно сильны, чтобы запустить алгоритм теоремы Савича (который дает алгоритм пространства O ( log 2 n ) ), но доказано, что они недостаточно сильны, чтобы делать асимптотически лучше. См. Статью «Плотные нижние границы для st-связности на модели NNJAG»L=NLstNLO(log2n), Эти нижние границы NNJAG показывают, что, если можно превзойти теорему Савича и даже получить , непременно придется придумать алгоритм, который сильно отличается от Савича.NLSPACE[o(log2n)]

Тем не менее, я не знаю каких-либо неожиданных, неожиданных формальных последствий от (за исключением очевидных). Опять же , это в первую очередь потому , что мы уже знаем , такие вещи , как N L = C O N L .L=NLNL=coNL

Райан Уильямс
источник
3
Райан, могут ли модели, в которых вы можете доказать нижнюю границу выполнять ненаправленную связность в пространстве O ( log n ) ? Если они являются неоднородными моделями, я думаю, что должно быть просто реализовать алгоритм, основанный на универсальных последовательностях обхода, даже в очень ограниченной моделиΩ(log2n)O(logn)
Лука Тревизан
@Luca, статья Райана, цитируемая Edmonds et al. отмечает, что ненаправленная связность может быть решена в пространстве и полиномиальном времени с помощью рандомизированного алгоритма с использованием универсальных последовательностей обхода. Я подозреваю, что он может быть дерандомизирован "а-ля" Рейнгольд, оставаясь внутри модели NNJAG, но я не проверял. O(logn)
Арнаб
1
Я думаю, что модель может выполнять ненаправленную связность на регулярных графах в пространстве . Страница 4 дает описание модели. Нам разрешается р гальки передвигаться на узлах графа (для нас, пусть р = 1 ), Q «состояния», и функция перехода , которая принимает состояние и индекс галечного узла, и выводит индекс ребра двигать гальку вдоль. (Ребра вершины v индексируются 0 , , d .) Используя q = n O ( 1 )O(logn)pp=1qv0,,dq=nO(1)состояния мы можем закодировать универсальную последовательность обхода. Использование пространства NNJAG определяется как которое в этом случае равно O ( log n ) . plogn+logqO(logn)
Райан Уильямс