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

46

Мы знаем, что LNLP и что LNLL2 polyL , где L2=DSPACE(log2n) . Мы также знаем , что polyLPпотому что у последнего есть полные проблемы при логарифмическом пространстве многократных сокращений, в то время как у первого нет (из-за теоремы о пространственной иерархии). Для того , чтобы понять взаимосвязь между polyL и P , это может помочь сначала понять взаимосвязь между L2 и P .

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

Как насчет более сильного LkP при k>2 или более слабого L1+ϵP при ϵ>0 ?

argentpepper
источник
4
@ OrMeir Недавно я добавил объяснение этого факта в статью в Википедии для polyL .
argentpepper
13
Я думаю, что следующее является очевидным следствием и особенно не удивительным: L2P будет означать, что LP , потому что в противном случае это противоречило бы пространственной иерархии LL2 .
Саджин Корот
12
Аккуратный вопрос! Я думаю, что это определенно стоит награды. Кстати, вот простое наблюдение, если , то D S P A C E ( n ) D T I M E ( 2 O ( L2P. Поэтому у нас есть более эффективный алгоритм для CNF-SAT, и мы опровергаем ETH (гипотеза экспоненциального времени). DSPACE(n)DTIME(2O(n))
Майкл Вехар
3
После комментария @ MichaelWehar импликация вытекает из стандартного аргумента заполнения, который распространяется на более слабые гипотезы: если находится в P , то любая проблема, которая может быть решена в линейном пространстве (включая проблему выполнимости), может быть решена во времени 2 O ( n 1L1+ϵP. 2O(n11+ϵ)
argentpepper
3
@SajinKoroth: Я думаю, что ваш комментарий, а также комментарии Майкла Вехара (и продолжение argentpepper) должны быть ответами ...
Джошуа Грохов

Ответы:

26

Следующее очевидное следствие: будет означать , LP и , следовательно , LP .L1+ϵPLPLP

По теореме о пространственной иерархии . Если L 1 + & epsi ; ⊆ Р , то LL 1 + & epsi ; ⊆ P .ϵ>0:LL1+ϵL1+ϵPLL1+ϵP

Саджин Корот
источник
Небольшая сноска: Если , то есть P N L или N L L . PLPNLNLL
Майкл Вехар
27

опровергнетгипотезуобэкспоненциальном времени.L2P

Если то по дополнительному аргументу D S P A C E ( n ) D T I M E ( 2 O ( L2P . Это означает, что проблема выполнимостиSATDSPACE(n) может быть решена за2o(n)шагов, опровергая гипотезу об экспоненциальном времени.DSPACE(n)DTIME(2O(n))SATDSPACE(n)2o(n)

В более общем случае, для k 1DSPACE(logkn)Pk1 подразумевает .SATDSPACE(n)DTIME(2O(n1k))

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

argentpepper
источник
Спасибо за расширение комментария! Я ценю это. :)
Майкл Вехар
1
Кроме того, последняя гипотеза также подразумевает, что находится в DSPACE ( n ) DTIME ( 2 O ( n 1)QBFn). 2O(n1k)
Майкл Вехар
8

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

Заставляет меня задуматься, к каким другим естественным и важным проблемам это относится: в но с их наиболее известным квазиполиномом с верхней верхней границей времени.L2

Джошуа Грохов
источник
1
Более конкретно, более общая проблема изоморфизма квазигрупп находится в , который является подклассом Lβ2FОLL . L2
argentpepper
1
Кроме того, проблема группового ранга (учитывая конечную группу G в качестве таблицы умножения и целое число k , имеет ли G порождающий набор мощности k ?) Также обладает этим свойством. Алгоритм представляет собой просто поиск по подмножествам G мощности k, но использует два важных факта: (1) каждая конечная группа имеет порождающий набор логарифмического размера и (2) членство в подгруппе находится в , что равноSL . L
argentpepper
1

Утверждение: если для некоторого k > 2 , то P log ( C FLКпК>2 и P N L .пжурнал(СFL)пNL

Предположим, что для некоторого k > 2 .LkPk>2

Из « границ памяти для распознавания контекстно-свободной и контекстно-зависимых языков », мы знаем , что . По теореме о пространственной иерархии мы знаем, что D S P A C E ( log 2 ( n ) ) D S P A C E (CFLDSPACE(log2(n)) .DSпAСЕ(журнал2(N))DSпAСЕ(журналК(N))

Следовательно, получаем .log(CFL)DSPACE(log2(n))DSPACE(logk(n))P

Также по теореме Савича мы знаем, что . Следовательно, мы получаем N L D S P A C E ( log 2 ( n ) ) D S P A C E ( log k ( nNLL2 .NLDSPACE(log2(n))DSPACE(logk(n))P

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