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

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

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

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

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