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

Наиболее важной задачей будущих исследований является получение нижней границы !(lg n) на операцию для некоторой динамической структуры данных в модели клеточного зонда с размером слова @(lg n). Милтерсен [ ] определяет набор технических условий для того, что считается решением такой задачи. В частности, задача должна быть проблемой динамической принадлежности языку.

Для задачи о частных суммах, хотя операция sum вполне изучена, testsum все еще не имеет строгих границ для определенных диапазонов параметров [ ]. Кроме того, получение строгих границ в модели битового зонда для частных сумм в Z2 представляется довольно сложной задачей.