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

Подход к реализации деревьев слияния с инструкциями AC0 известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины <math>AC^0</math>? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций <math>AC^0</math>?

Можно ли сделать время обновления детерминированным при решении динамической задачи? В частности, можно ли реализовать поиск ван Эмде Боаса с быстрым детерминированным обновлением? Это очень интересная задача, находящая применение в детерминированных словарях [ ]. Кроме того, можно ли детерминированным образом обновлять узлы слияния за константное время? Атомарные кучи [11] достигают этого результата при поиске только среди <math>(lg \; n)^{\varepsilon}</math> элементов, а не <math>b^{\varepsilon}</math>.

Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить <math>t+u = o(t_q)</math>, сохранив при этом эффективное время запроса?