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

Исходя из вышесказанного, задача состоит в том, чтобы доказать хорошие нижние границы для операции '''sum''' даже в недетерминистской модели. Недетерминизм поколебал представление о том, что при анализе эпохи 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>, трижды логарифмически удаленную от верхней.