Отделение Logspace от полиномиального времени

Ясно, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Существует множество классов сложности между и . Примеры включают , , , , , . Широко распространено мнение , что .P L P N L L o g C F L N C i S A C i A C i S C i L ≠ $L$$P$$L$$P$$NL$$LogCFL$$NC^i$$SAC^i$$AC^i$$SC^i$$L \neq P$

В одном из моих сообщений в блоге я уже два подхода (наряду с соответствующими догадками) на доказательство . Оба эти подхода основаны на программах ветвления и разнесены на 20 лет !! Существуют и другие подходы и / или Гипотезы к разделению от (или) , разделяющие любые промежуточные классы между и .L P L $L \neq P$$L$$P$$L$$P$

Нижние границы глубины контура (эквивалентно нижним границам размера формулы), вероятно, являются наиболее естественным подходом: нижняя граница глубины Super- для задачи в отделяет от , и Техника сложности коммуникации Карчмера-Вигдерсона может быть естественной для этого.P P $\log^2(n)$$\mathsf P$$\mathsf P$$\mathsf L$

[1] доказывает нижнюю границу для случаев минимального потока, чьи размеры в битах достаточно велики (но все еще линейны) по сравнению с размером графа, и, кроме того, доказано, что если бы можно было показать такую ​​же нижнюю границу для входов достаточно малого размера битовый размер подразумевал бы (и, следовательно, P ≠ L ). На высоком уровне это то же самое, что и ответ Ноама в том, что речь идет о проверке нижних границ глубины контура (= нижних границ размера формулы), но, похоже, это совсем другое направление, чем в играх Карчмера-Вигдерсона.$\mathsf{P} \neq \mathsf{NC}$$\mathsf{P} \neq \mathsf{L}$

Более подробно [1] показывает следующее. Используя те же обозначения, что и в статье, пусть обозначает язык потока минимальной стоимости. Мы можем думать о языке потока минимальных издержек на n- вершинных графах, обозначенном L ( n ) , как подмножество Z k ( n ) для некоторого k ( n ) = Θ ( n 2 ) , с целыми числами, закодированными битовыми строками , Пусть B ( a , n ) обозначает множество всех векторов в Z k ( n $L$$n$$L(n)$$\mathbb{Z}^{k(n)}$$k(n) = \Theta(n^2)$$B(a,n)$$\mathbb{Z}^{k(n)}$где каждая целочисленная координата имеет размер не более . Для функции f ( x 1 , … , x k ) (позже мы укажем, что это за функция), мы говорим, что f разделяет L ( n ) внутри B ( a , n ), если точки в L ( n ) ∩ B ( a , n ) как раз те, что → x ∈ B ( a $an$$f(x_1, \dotsc, x_k)$$f$$L(n)$$B(a,n)$$L(n) \cap B(a,n)$ такой, что f ( → x ) = 1 .$\vec{x} \in B(a,n)$$f(\vec{x}) = 1$

$L(n)$$B(a,n)$M ≤ 2 n / d x 1 , … , x k a < 1 / ( 2 d ) P ≠ N $\det(M(\vec{x}))$$M$$\leq 2^{n/d}$$x_1, \dotsc, x_k$$a < 1/(2d)$$\mathsf{P} \neq \mathsf{NC}$

Соотношение между битовой привязкой и размерной границей имеет решающее значение. В той же газете он показал:2 н /$an$$2^{n/d}$

Теорема [1, теорема 7.4]. Гипотеза предыдущего предложения справедлива для всех достаточно больших битовых оценок .$a$

Доказательство вышеупомянутой теоремы использует некоторые тяжелые молотки в качестве черных ящиков, но в остальном элементарно (примечание: «элементарный» « легкий »). А именно, он использует границу Милнора-Тома для числа связанных компонент вещественного полуалгебраического многообразия (ту же самую границу, которую Бен-Ор использовал для доказательства нижних оценок на элементность / сортировку элементов в реальной модели дерева вычислений), разложение Коллинза ( используется для доказательства эффективного исключения квантификатора над ), аргумента общей позиции и нескольких других идей. Тем не менее, все эти методы зависят только от степени задействованных полиномов, и поэтому не могут быть использованы для доказательства как в приведенном выше предложении (действительно, [1, проп. 7.5] строит полиномR P ≠ N C г дет г $\neq$$\mathbb{R}$$\mathsf{P} \neq \mathsf{NC}$$g$ такой же степени, что и , так что вышеприведенное утверждение не выполняется с вместо ). Анализ этой ситуации и поиск свойств, которые выходили за рамки степени, были одним из вдохновителей GCT.$\det$$g$$\det$

[1] К. Малмулей. Нижние границы в параллельной модели без битовых операций . SIAM J. Comput., 28 (4), 1460–1509, 1999

Это сделало мой день, когда мой друг Джеймс сказал мне, что эта нить давно была разожжена. Спасибо тебе за это.

Кроме того, у меня было желание поделиться некоторыми интересными ссылками, которые имеют отношение к L против журнала (DCFL) против журнала (CFL). Хорошего дня!

http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1

http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true

http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1

http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata

эта новая статья была только что отмечена Лукой Ачето в его блоге как лучшая студенческая статья EATCS на ICALP 2014 и имеет новый способ разделения NL / P:

• Результаты твердости для непустоты пересечения Вехар

  Мы тщательно пересматриваем конструкцию Karakostas, Lipton и Viglas (2003), чтобы показать, что проблема непустоты пересечения для DFA (детерминированных конечных автоматов) характеризует класс сложности NL. В частности, если он ограничен двоичным алфавитом рабочей ленты, то существуют константы и , так что для каждого пересечения незаполненность для DFA разрешима в пространстве , но не разрешима в пробел. Мы оптимизируем конструкцию, чтобы показать для произвольного числа непустоты пересечения DFA неразрешимую вc 2 k k c 1 k log ( n ) c 2 k log ( n ) o ( $c_1$$c_2$$k$$k$$c_1 k \log(n)$$c_2 k \log(n)$f(k)=o(k)kknf(k)ckkn$o \left( \frac{n}{\log(n) \log(\log(n))} \right)$Космос. Кроме того, если существует функция такая, что для каждого пересечения незаполненность для DFA разрешима за время, то P ≠ NL. Если не существует константы такой, что для каждого пересечения непустота для DFA разрешима за времени, то P не содержит никакого класса пространственной сложности, большего, чем NL.$f(k) = o(k)$$k$$k$$n^{f(k)}$$c$$k$$k$$n^c$