# Provable gaps between decision tree complexity and "true" complexity

The title is a little misleading: but hopefully the question isn't:

Grønlund and Pettie's new result showing that 3SUM has only $O(n^{3/2})$ decision tree complexity got me wondering:

Is there a simple example of a problem with a decision tree complexity of $O(f)$ but that admits a lower bound (in a more detailed model) of $\omega(f)$ ?

In other words, how should the result on 3SUM change our view of the possibility of getting a significantly lower than $n^2$ upper bound on the complexity of the problem ?

• Element distinctness can be solved with a constant-depth binary decision tree. ("Are all the elements distinct?") But we need $\Omega(n\log n)$ depth to solve the problem using using linear decision trees. Apr 12 '14 at 1:31
• The decision tree model is an information theoretic model: Once you have learned enough information about your input that the answer is uniquely determined from this information, you are done. It doesn't matter if determining the answer from this information is undecidable. So for example if the input is an n-bit binary string encoding a Turing machine, and the question is whether this TM halts, a decision tree of depth n can trivially solve this problem since it knows all n bits, but no algorithm can solve this problem. Apr 12 '14 at 3:09
• Maybe I should have said 'example of a simple problem' instead :). Apr 12 '14 at 18:15

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$. A similar result can be deived from a later algorithm of Meiser for point location in hyperplane arrangements. Of course the problem is NP-hard.
Here is an example of a trivial gap between decision-tree and algorithmic complexity. The randomized decision tree complexity of local sorting (orienting a vertex-weighted graph) is $O(n\log(\frac{m+n}{n}))$ whereas the size of the input is $\Theta(n+m)$. Any algorithm needs to read the input, so there's a separation whenever $m=\omega(n)$. See Goddard, Kenyon, King, Schulman (SICOMP 1993).