Поиск предков: различия между версиями

Все нижние границы до выхода работы [15] были показаны на модели коммуникативной игры. Айтай [ ] первым представил суперконстантную нижнюю границу. Его результаты, с поправкой Милтерсена [12], показывают, что для полиномиального объема памяти существует n как функция от £, позволяющая получить время запроса £?(y/lg~£), и аналогично существует I как функция от n, позволяющая получить сложность запроса Q (3lgn).

Милтерсен и другие [ ] пересмотрели доказательство Айтая, распространив его на рандомизированные алгоритмы. Что более важно, они отразили суть доказательства в лемме о независимом исключении раунда, которая служит важным инструментом при доказательстве нижних границ в асимметричной коммуникации.

Бим и Фич [ ] улучшили нижние границы Айтая до и ^2(y'lg n/lglg n), соответственно. Сен и Венкатеш  [17] позже представили улучшенную лемму об исключении раунда, которая обосновывает эти нижние границы в том числе и для рандомизированных алгоритмов.

Наконец, используя лемму о сжатии сообщений из работы [6] (являющемся альтернативой исключению раунда), Петрашку и Торуп [15] предложили оптимальный компромисс для коммуникативных игр. Он также является оптимальной нижней границей в других моделях, в которых S > n1+", но не подходит для меньшего объема памяти.

Что более важно, в [ ] были разработаны первые инструменты для доказательства нижних границ, превышающих коммуникационную сложность, для случаев S = n1+o(1). Здесь впервые было проведено разделение между структурой данных полиномиального размера и структурой размера, близкого к линейному. Его принципиально невозможно получить при помощи нижней границы для прямых коммуникаций, поскольку редукция к коммуникативным играм зависит только от lg S.

С технической точки зрения идея [ ] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается отклонить большую часть запросов, прежде чем приступить к зондированию.