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

На интуитивном уровне их аргументация выглядит следующим образом. В жестком экземпляре будет <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>.

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

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

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

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

Интуитивно понятно, что если размер слова равен <math>b = 1</math>, то нижняя граница связности должна быть примерно <math>\Omega(lg^2 \; n)</math>, поскольку для запроса требуется <math>\Omega(lg \; n)</math> бит из каждой эпохи. Однако исключить что-либо, кроме нулевых зондирований в эпоху, оказывается сложно по той же причине, по которой сложен недетерминированный случай. Не давая вполне удовлетворительного понимания этой проблемы, Петрашку и Тарница [7] используют большой набор трюков, чтобы продемонстрировать нижнюю границу <math>\Omega((lg \; n/lg \; lg \; n)^2)</math> для динамической связности. Более того, они рассматривают проблему частных сумм в <math>\mathbb{Z}_2</math> и показывают нижнюю границу <math>\Omega(lg \; n/lg \; lg \; lg \; n)</math>, трижды логарифмически удаленную от верхней.