Нижняя граница для динамической связности: различия между версиями

Динамические деревья (''Dynamic trees'')

'''connected'''(u, v): проверка, находятся ли u и v в одной и той же связной компоненте.

Пусть <math>m</math> – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за <math>t_u</math> сложность вставки и удаления, а за <math>t_q</math> – сложность проверки.

Нижние границы для задачи о динамической связности тесно связаны с нижними границами для другой классической задачи – поддержки частных сумм. Формально, задача состоит в том, чтобы поддерживать массив A[1..n], выполняя следующие операции:

'''update'''(k, <math>\Delta</math>: обновление <math>A[k] \leftarrow \Delta</math>;  

Чтобы полностью сформулировать задачу, будем считать, что элементы <math>A[i]</math> берутся из произвольной группы <math>G</math>, содержащей не менее <math>2^{\delta}</math> элементов. В модели клеточного зонда с b-битными ячейками (клетками) обозначим за <math>t_u^{\Sigma}</math> сложность обновления (update), а за <math>t_q^{\Sigma}</math> – сложность проверки (testsum) (которая также является нижней границей sum).

Заметим, что это совпадает с хрестоматийной верхней границей при использовании дополненных деревьев. Можно построить сбалансированное бинарное дерево над <math>A[1], ..., A[n]</math> и хранить в каждом внутреннем узле сумму его поддерева. Тогда обновления и запросы затрагивают <math>O(lg \; n)</math> узлов (и тратят <math>O(\lceil \delta\b \rceil)</math> времени в каждом из них из-за размера группы). Чтобы уменьшить время запросов, можно использовать [[B-Дерево|B-дерево]].

Чтобы реализовать операцию '''update'''(x, <math>\pi</math>), сначала удаляются все ребра между столбцами x и x + 1, а затем вставляются новые ребра согласно <math>\pi</math>. Это дает <math>t_u^{\Sigma} = O(2n \cdot t_u)</math>. Для реализации операции '''testsum'''(x, <math>\pi</math>) можно использовать <math>n</math> запросов '''connected''' между парами точек <math>(1, у) \rightsquigarrow (х + 1, \pi(у))</math>. Тогда <math>t_q^{\Sigma} = O(n \cdot t_q)</math>. Заметим, что запрос '''sum''' не может быть реализован так же просто. Динамическая связность является основным мотивом для изучения запроса '''testsum'''.

На интуитивном уровне их аргументация выглядит следующим образом. В жестком экземпляре будет <math>n</math> случайных обновлений, за которыми следует один случайный запрос. Оставим <math>r \ge 2</math> для последующего определения. Идя ''назад'' по времени от запроса, можно сгруппировать обновления в экспоненциально растущие ''эпохи'': последние <math>r</math> обновлений – это эпоха 1, более ранние <math>r^2</math> обновлений – эпоха 2 и т. д. Обратите внимание, что номера эпох увеличиваются с течением времени, и всего существует <math>O(log_r \; n)</math> эпох.

Для некоторой эпохи <math>i</math> рассмотрим раскрытие в запросе всех обновлений, выполненных во все эпохи, отличные от <math>i</math>. Тогда запрос сводится к запросу частных сумм среди обновлений в эпоху <math>i</math>. Если запрос не касается индекса ниже минимального индекса, обновленного в эпоху <math>i</math>, ответ на запрос остается равномерно случайным, то есть имеет <math>\delta</math> бит энтропии. Более того, даже если дано, скажем, <math>r_i \delta/100</math> бит информации об эпохе <math>i</math>, ответ все равно имеет в среднем <math>\Omega(\delta)</math> бит энтропии. Это происходит потому, что запрос и обновления в эпоху <math>i</math> равномерно случайны, поэтому запрос может касаться любой частной суммы этих обновлений равномерно случайным образом. Каждая из частных сумм <math>r_i</math> является независимой случайной переменной от энтропии <math>\delta</math>.

2. В эпохи <math>1, ..., i - 1</math> было записано <math>b t_u^{\Sigma} \cdot \sum_{j = 1}^{i - 1} r^j \le b t_u^{\Sigma} \cdot 2 r^{i - 1}</math> бит. Это меньше, чем <math>r_i \delta/100</math> бит информации для <math>r > 200 t_u^{\Sigma}</math> (вспомним предположение <math>\delta = b</math>). Из вышесказанного следует, что ответ на запрос все еще имеет <math>\Omega(\delta)</math> бит энтропии.

3. Поскольку значение <math>i</math> равномерно случайно среди <math>\Theta(log_r \; n)</math> эпох, запрос делает ожидаемое число <math>\Theta(t_q^{\Sigma}/log_r \; n)</math> зондирований ячеек из эпохи <math>i</math>. Все запросы, которые не делают ни одного зондирования ячеек в эпоху <math>i</math>, получают фиксированный ответ (энтропия 0), а все остальные запросы получают ответы с энтропией менее <math>\delta</math>. Поскольку средний запрос имеет энтропию <math>\Omega(\delta)</math>, запрос должен зондировать ячейку из эпохи <math>i</math> с константной вероятностью. Это означает, что <math>t_q^{\Sigma} / log_r \; n = \Omega(1)</math>, а <math>\sum = \Omega(log_r \; n) = \Omega(lg \; n/lg \; t_u^{\Sigma})</math>.

Следует оценить двойственность между техникой доказательства и естественными верхними границами, основанными на иерархии. Рассмотрим верхнюю границу, основанную на дереве степени <math>r</math>. Последние <math>r</math> случайных обновлений (эпоха 1), вероятно, равномерно распределены в массиве. Это означает, что обновления касаются разных дочерних элементов корня. Аналогично, <math>r^2</math> обновлений в эпоху 2, скорее всего, коснутся каждого узла на втором уровне дерева, и так далее. Нижняя граница свидетельствует, что запрос должен пройти путь от корня к листьям, прощупывая узел на каждом уровне дерева (что эквивалентно одной ячейке из каждой эпохи).

Несмотря на значительное усовершенствование техники нижних границ, нижняя граница <math>\Omega(lg \; n/lg \; lg \; n)</math> не была улучшена до 2004 года. Тогда Петрашку и Демейн [6] показали оптимальное ограничение <math>t_q^{\Sigma} lg(t_u^{\Sigma}/t_q^{\Sigma}) = \Omega(lg \; n)</math>, что означает <math>max \{ t_u^{\Sigma}, t_q^{\Sigma} \} = \Omega(lg \; n)</math>. Для простоты нижеследующее обсуждение пренебрегает этим компромиссом и просто набрасывает нижнюю границу <math>\Omega(lg \; n)</math>.

Теперь рассмотрим два «братских» поддерева, каждое из которых содержит <math>k</math> операций. Предполагается, что <math>k/2</math> обновлений в левом поддереве и <math>k/2</math> запросов в правом поддереве будут чередоваться в пространстве индексов. Таким образом, запросы в правом поддереве запрашивают <math>\Omega(k)</math> различных частных сумм обновлений в левом поддереве. Таким образом, правому поддереву «нужно» <math>\Omega(k \delta)</math> бит информации о левом поддереве, и эта информация может поступать только из ячеек, записанных в левом поддереве и прочитанных в правом. Отсюда следует нижняя граница в <math>\Omega(k)</math>) зондов, связанных с родителем «братских» поддеревьев. Эта граница линейна по числу листьев, так что, суммируя по всему дереву, мы получаем полную нижнюю границу <math>\Omega(n \; lg \; n)</math>, или стоимость <math>\Omega(lg \; n)</math> на операцию.

Как ни удивительно, но Петрашку и Тарнице [7] удалось воспроизвести оптимальный компромисс теоремы 1 с минимальными изменениями рассуждений об эпохах. В старой версии этих рассуждений информация, раскрываемая эпохами <math>1, ..., i - 1</math> об эпохе <math>i</math>, ограничивалась количеством ячеек, записанных в эти эпохи. Ключевая идея заключается в том, что не менее удачным ограничением является количество ячеек, прочитанных в эпохи <math>1, ..., i - 1</math> и записанных в эпоху <math>i</math>.

В принципе, все операции чтения ячеек из эпохи <math>i - 1</math> могут читать данные из эпохи <math>i</math>, что делает эти две границы идентичными. Однако можно рандомизировать построение эпох, вставляя запрос после непредсказуемого количества обновлений. Такая рандомизация «сглаживает» распределение эпох, из которых считываются ячейки, то есть запрос считывает <math>O(t_q^{\Sigma}/log_r \; n)</math> ячеек из каждой эпохи, что выходит за рамки случайности в построении эпохи. Тогда <math>O(r^{i - 1})</math>обновлений в эпохи <math>1, ..., i - 1</math> читают только <math>O(r^{i-1} \cdot t_u^{\Sigma}/log_r \; n)</math> ячеек из эпохи <math>i</math>. Этой информации недостаточно, если <math>r \gg t_u^{\Sigma}/log_r \; n = \Theta(t_u^{\Sigma}/t_q^{\Sigma})</math>, из чего следует, что <math>t_q^{\Sigma} = \Omega(log_r \; n) = Omega(lg \; n/lg(t_u^{\Sigma}/t_q^{\Sigma}))</math>.

Нижние границы, описанные выше, основаны на том, что запрос суммы должен выводить Q (<5) бит информации о каждом запросе. Если мы имеем дело с запросом о принятии решения для testsum, то аргумент, основанный на энтропии вывода, уже не работает.

Наиболее удачной идеей для запросов на принятие решений было преобразование их в запросы с небулевым результатом в расширенной модели клеточного зонда, допускающей недетерминизм. В этой модели алгоритм запроса может порождать произвольное количество вычислительных потоков. Каждый поток может сделать tq клеточных зондирований, после чего он должен либо завершиться ответом «отказ», либо вернуть ответ на запрос. Все потоки, не завершающиеся отказом, должны возвращать один и тот же результат. В этой модели запрос с произвольным результатом эквивалентен запросу на принятие решения, поскольку можно просто недетерминистским образом угадать ответ, а затем проверить его.

Исходя из вышесказанного, задача состоит в том, чтобы доказать хорошие нижние границы для суммы даже в недетерминистской модели. Недетерминизм поколебал представление о том, что при анализе эпохи i имеют значение только запросы к ячейкам эпохи <math>i</math>. Проблема в том, что запрос может не знать, какие из его зондирований действительно относятся к эпохе <math>i</math>. Зонд, считывающий ячейку из предыдущей эпохи, предоставляет по крайней мере некоторую информацию об эпохе <math>i</math>: ни одно обновление в эту эпоху не решило перезаписать клетку. Ранее это не было проблемой, поскольку целью было только исключить случай, когда в эпоху <math>i</math> существует ноль зондирований. Теперь, однако, различные потоки могут зондировать любую ячейку в памяти, и невозможно определить, какие потоки на самом деле избегают зондирования чего-либо в эпоху <math>i</math>. Другими словами, между эпохой <math>i</math> и запросом существует скрытый канал связи, в котором эпоха может использовать выбор того, какие ячейки записывать, чтобы передать информацию запросу.

Существует две основные стратегии для работы с алгоритмами недетерминированных запросов. Хасфельдт и Раухе [4] приводят доказательство, основанное на некоторых интересных наблюдениях о комбинаторике недетерминированных запросов. Петрашку и Демейн [6] используют силу самого недетерминизма для вывода небольшого сертификата, исключающего бесполезные зондирования ячеек. Из последнего результата вытекает оптимальная нижняя граница Теоремы 1 для '''testsum''' и, следовательно, логарифмическая нижняя граница для динамической связности.

Описанная выше схема опирается на фиксацию всех обновлений в эпохи, отличные от <math>i</math>, к среднему значению и утверждение, что ответ на запрос все равно имеет большую вариативность, зависящую от обновлений в эпоху <math>i</math>. Это верно для задач агрегирования, но не для задач поиска. Если искомый элемент найден с равной вероятностью в любой эпохе, то фиксация всех остальных эпох делает эпоху <math>i</math> нерелевантной с вероятностью 1 - 1/(logr n).

Олстрап и др. [] предложили очень интересное усовершенствование этой техники, доказав нижние границы Q (lg n/ lg lg n) для впечатляющей коллекции задач поиска. Интуитивно их идея заключается в рассмотрении O(logr n) альтернативных историй обновлений, выбранных независимо друг от друга случайным образом. Эпоха <math>i</math> релевантна хотя бы в одной из историй с константной вероятностью. С другой стороны, даже если известно, что эпохи с 1 по i - 1 узнали об эпохе <math>i</math> во всех историях, ответить на случайный запрос все равно сложно.

Интуитивно понятно, что если размер слова равен b = 1, то нижняя граница связности должна быть примерно £?(lg 2n), поскольку для запроса требуется £?(lg n) бит из каждой эпохи. Однако исключить что-либо, кроме нулевых зондирований в эпоху, оказывается сложно по той же причине, по которой сложен недетерминированный случай. Не давая вполне удовлетворительного понимания этой проблемы, Петрашку и Тарнифа [ ] используют большой набор трюков, чтобы продемонстрировать нижнюю границу £?((lg n/lglg n)2) для динамической связности. Более того, они рассматривают проблему частных сумм в Z2 и показывают нижнюю границу £?(lg n/lglg lg n), трижды логарифмически удаленную от верхней.

Наиболее важной задачей будущих исследований является получение нижней границы !(lg n) на операцию для некоторой динамической структуры данных в модели клеточного зонда с размером слова @(lg n). Милтерсен [ ] определяет набор технических условий для того, что считается решением такой задачи. В частности, задача должна быть проблемой динамической принадлежности языку.

Для задачи о частных суммах, хотя операция sum вполне изучена, testsum все еще не имеет строгих границ для определенных диапазонов параметров [ ]. Кроме того, получение строгих границ в модели битового зонда для частных сумм в Z2 представляется довольно сложной задачей.