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

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

Известно, что . Литература по derandomization из R L является довольно убедительным , что R L = L . Кто-нибудь знает о каких-то статьях или идеях, убеждая, что N L ≠ L ?$NL \subset L^2$$RL$$RL=L$$NL\neq L$

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

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

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

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

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