Каковы последствия

46

Мы знаем, что $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ и что $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$ , где $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$ . Мы также знаем , что $\mathsf{polyL} \neq \mathsf{P}$ потому что у последнего есть полные проблемы при логарифмическом пространстве многократных сокращений, в то время как у первого нет (из-за теоремы о пространственной иерархии). Для того , чтобы понять взаимосвязь между $\mathsf{polyL}$ и $\mathsf{P}$ , это может помочь сначала понять взаимосвязь между $\mathsf{L}^2$ и $\mathsf{P}$ .

Каковы последствия $\mathsf{L}^2 \subseteq \mathsf{P}$ ?

Как насчет более сильного $\mathsf{L}^{k} \subseteq \mathsf{P}$ при $k>2$ или более слабого $\mathsf{L}^{1 + \epsilon} \subseteq \mathsf{P}$ при $\epsilon > 0$ ?

cc.complexity-theory complexity-classes conditional-results structural-complexity argentpepper
источник

4

@ OrMeir Недавно я добавил объяснение этого факта в статью в Википедии для polyL .

argentpepper

13

Я думаю, что следующее является очевидным следствием и особенно не удивительным:

L^{2} \subseteq P

$L^2 \subseteq P$ будет означать, что

L \neq P

$L \neq P$ , потому что в противном случае это противоречило бы пространственной иерархии

L ⊊ L^{2}

$L \subsetneq L^2$ .

Саджин Корот

12

Аккуратный вопрос! Я думаю, что это определенно стоит награды. Кстати, вот простое наблюдение, если

, то

L^{2} \subseteq P

$L^2 \subseteq P$

. Поэтому у нас есть более эффективный алгоритм для CNF-SAT, и мы опровергаем ETH (гипотеза экспоненциального времени).

D S P A C E (n) \subseteq D T I M E (2^{O (\sqrt{n})})

$DSPACE(n) \subseteq DTIME(2^{O(\sqrt{n})})$

Майкл Вехар

3

После комментария @ MichaelWehar импликация вытекает из стандартного аргумента заполнения, который распространяется на более слабые гипотезы: если

находится в

, то любая проблема, которая может быть решена в линейном пространстве (включая проблему выполнимости), может быть решена во времени

L^{1 + ϵ}

$L^{1 + \epsilon}$

P

$P$

.

2^{O (n^{\frac{1}{1 + ϵ}})}

$2^{O\left(n^{\frac{1}{1 + \epsilon}}\right)}$

argentpepper

3

@SajinKoroth: Я думаю, что ваш комментарий, а также комментарии Майкла Вехара (и продолжение argentpepper) должны быть ответами ...

Джошуа Грохов

26

Следующее очевидное следствие: будет означать , и , следовательно , . $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ $\mathsf{L} \subsetneq \mathsf{P}$ $\mathsf{L} \neq \mathsf{P}$

По теореме о пространственной иерархии . Если , то . $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$ $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ $\mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$

Саджин Корот
источник

Небольшая сноска: Если

, то есть

или

.

P \neq L

$P \neq L$

P \neq N L

$P \neq NL$

N L \neq L

$NL \neq L$

Майкл Вехар

27

$\newcommand{\DSPACE}{\mathsf{DSPACE}} \newcommand{\L}{\mathsf{L}} \newcommand{\P}{\mathsf{P}} \newcommand{\DTIME}{\mathsf{DTIME}}$

опровергнетгипотезуобэкспоненциальном времени. $\L^2 \subseteq \P$

Если то по дополнительному аргументу $\L^2 \subseteq \P$ . Это означает, что проблема выполнимости может быть решена зашагов, опровергая гипотезу об экспоненциальном времени. $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$ $\mathsf{SAT} \in \DSPACE(n)$ $2^{o(n)}$

В более общем случае, для $\DSPACE(\log^{k} n) \subseteq \P$ $k\geq1$ подразумевает . $\mathsf{SAT} \in \DSPACE(n) \subseteq \DTIME(2^{O(n^{\frac{1}{k}})})$

(Этот ответ дополнен комментарием @MichaelWehar.)

argentpepper
источник

Спасибо за расширение комментария! Я ценю это. :)

Майкл Вехар

1

Кроме того, последняя гипотеза также подразумевает, что

находится в DSPACE (

)

DTIME (

Q B F

$QBF$

n

$n$

\subseteq

$\subseteq$

).

2^{O (n^{\frac{1}{k}})}

$2^{O(n^{\frac{1}{k}})}$

Майкл Вехар

8

Групповой изоморфизм (с группами, заданными в виде таблиц умножения) был бы в P. Lipton, Snyder и Zalcstein показали, что эта проблема находится в , но она все еще открыта, находится ли она в P. Лучшая текущая верхняя граница равна -время, и поскольку оно сводится к изоморфизму графа, является существенным препятствием для помещения графа iso в P. $\mathsf{L}^2$ $n^{O(\log n)}$

Заставляет меня задуматься, к каким другим естественным и важным проблемам это относится: в но с их наиболее известным квазиполиномом с верхней верхней границей времени. $\mathsf{L}^2$

Джошуа Грохов
источник

1

Более конкретно, более общая проблема изоморфизма квазигрупп находится в

, который является подклассом

β_{2} F O L L

$\beta_2 \mathsf{FOLL}$

.

L^{2}

$\mathsf{L}^2$

argentpepper

1

Кроме того, проблема группового ранга (учитывая конечную группу G в качестве таблицы умножения и целое число k , имеет ли G порождающий набор мощности k ?) Также обладает этим свойством. Алгоритм представляет собой просто поиск по подмножествам G мощности k, но использует два важных факта: (1) каждая конечная группа имеет порождающий набор логарифмического размера и (2) членство в подгруппе находится в

, что равно

S L

$\mathsf{SL}$

.

L

$\mathsf{L}$

argentpepper

1

Утверждение: если для некоторого , то $L^k \subseteq P$ $k > 2$ и . $P \neq \log(CFL)$ $P \neq NL$

Предположим, что для некоторого . $L^k \subseteq P$ $k > 2$

Из « границ памяти для распознавания контекстно-свободной и контекстно-зависимых языков », мы знаем , что . По теореме о пространственной иерархии мы знаем, что $CFL \subseteq DSPACE(\log^2(n))$ . $DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n))$

Следовательно, получаем . $\log(CFL) \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Также по теореме Савича мы знаем, что . Следовательно, мы получаем $NL \subseteq L^2$ . $NL \subseteq DSPACE(\log^2(n)) \subsetneq DSPACE(\log^k(n)) \subseteq P$

Майкл Вехар
источник

Каковы последствия

Ответы: