Эффективные алгоритмы логарифмического пространства

17

Легко видеть, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Многие известные алгоритмы логарифмического пространства (например, ненаправленная st-связность, изоморфизм плоских графов) работают в где безумно велико. $L$ $P$ $O(n^k)$ $k$

Я ищу примеры естественных проблем, которые, как известно, разрешимы одновременно в детерминированном логарифмическом пространстве и времени, где . В 10. нет ничего особенного. Глядя на известные в настоящее время алгоритмы пространства журналов, я думаю, что достаточно интересен. $O(n^k)$ $k \leq 10$ $k \leq 10$
Aleliunas et al. показал, что ненаправленная st-связность находится в (рандомизированное пространство журналов). Время выполнения их алгоритма . Существуют ли естественные проблемы, которые могут быть решены одновременно в и линейном времени (или) вблизи линейного времени, т. Е. времени? $RL$ $O(n^3)$ $RL$ $O(n{\log}^i{n})$

Изменить: Чтобы сделать вещи более интересными, давайте посмотрим на проблемы, которые, по крайней мере, трудно. $NC^1$

cc.complexity-theory space-bounded space-time-tradeoff Шива Кинтали
источник

Есть ли анализ времени в версии теоремы Курселя для логического пространства? eccc.uni-trier.de/report/2010/062

Сянь-Чи Чанг 1 之

10

Я предполагаю, что достижимость планарного DAG (SSPD) с одним источником с одним приемником имеет алгоритм пространства журналов с умеренным временем работы ( ?). Я не очень уверен насчет алгоритма планарной доступности DAG (SMPD) с несколькими источниками. $O(n^2)$

Ссылка: Эрик Аллендер, Дэвид А. Микс Баррингтон, Танмой Чакраборти, Самир Датта, Самбуддха Рой: проблемы достижимости плоского и сеточного графа. Теория вычислений. Сист. 45 (4): 675-723 (2009)

Кроме того, новый алгоритм логарифмического пространства для тестирования планарности и встраивания выполняется за умеренно полиномиальное время (конечно, по модулю ненаправленной достижимости)

Ссылка: Самир Датта, Гаутам Пракрия: Повторное тестирование на плоскостность CoRR abs / 1101.2637: (2011)

Наконец, вот простая игрушка, которая имеет алгоритм пространства журналов со скромным временем выполнения (по модулю ненаправленной достижимости), а именно. Внешний планарный изоморфизм.

SamiD
источник

1

Алгоритм SSPD равен

после того, как найдено плоское вложение, и использует тот факт, что существуют линейные, проходящие через лог-пространство пути «крайний левый» и «крайний правый» пути от любой вершины до приемника или источник любой вершины (назовите эти «внешние» пути). Чтобы найти путь от

до

, проверьте, совпадают ли вершины на внешних путях от u до раковины по внешним путям от источника к v.

O (n^{2})

$O(n^2)$

u

$u$

v

$v$

Деррик Столи

9

Этот ответ является скорее игрушечной проблемой, чем реальной проблемой исследования.

Мой типичный пример алгоритма пространства лога, который нужно передать друзьям-программистам, - это следующая загадка:

$n$

$O(\log n)$

Переместите первый указатель в списке на один шаг.
Продвиньте второй указатель в списке на два шага.
Если любой указатель находит конец, верните false.
Если узлы указывают на один и тот же узел, верните true.
В противном случае повторите итерацию.

$n$ $n$

Деррик Стоули
источник

3

N C^{1}

$NC^1$

3

$O(n)$

$NC^1$

Нил Кришнасвами
источник

2

Поскольку вы меняете график, это не алгоритм пространства журнала, где входная лента должна быть доступна только для чтения. Это интересный алгоритм сам по себе.

Деррик Стоули

Эффективные алгоритмы логарифмического пространства

Ответы: