Обеспечиваемые разрывы между сложностью дерева решений и «истинной» сложностью

Название немного вводит в заблуждение, но, надеюсь, вопрос не в следующем:

Новый результат Грёнлунда и Петти, показывающий, что 3SUM имеет только сложность дерева решений, заставил меня задуматься:$O(n^{3/2})$

Есть ли простой пример проблемы со сложностью дерева решений но допускающей нижнюю границу (в более детальной модели) ?$O(f)$$\omega(f)$

Другими словами, как результат на 3SUM должен изменить наше представление о возможности получения значительно более низкой, чем верхней границы сложности задачи?$n^2$

Meyer auf der Heide описал неоднородное семейство линейных деревьев решений для Subset Sum с глубиной . Аналогичный результат может быть получен из более позднего алгоритма Мейзера для определения местоположения в расположениях гиперплоскости. Конечно, проблема NP-сложная.$O(n^4\log n)$

$O(n\log(\frac{m+n}{n}))$$\Theta(n+m)$$m=\omega(n)$