<p>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).</p>

CC BY-SA 3.0
2014-04-15T17:52:37.150Z
Let me disagree a bit. In the RAM model, we do not necessarily need to read the whole input. In the Turing machine model, there are many trivial problems that can be solved faster with a decision-tree (or on a RAM machine). Also see Robin's comment to the original question.
domotorp
CC BY-SA 3.0
2014-04-15T17:20:25.477Z
2014-04-15T17:20:25.477Z
Seth Pettie
<p>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.</p>

CC BY-SA 3.0
2014-04-12T03:09:25.467Z
If I wanted to be REALLY PEDANTIC I'd point out that being NP-hard is not a firm lower bound. but that's a good example of the spirit of what I'm looking for.
Suresh Venkat
CC BY-SA 3.0
2014-04-12T14:05:02.437Z
Yeah, but we don't know how to prove firm lower bounds.
Jeffε
CC BY-SA 3.0
2014-04-16T15:05:48.897Z
@JɛﬀE Do you maybe know of a nice write up or exposition of this result? I find the original very hard to follow, some definitions are not clear at all to me.
domotorp
CC BY-SA 3.0
2014-04-16T18:25:38.267Z
At least the basic definitions are described in [my paper on linear degeneracy problems](http://www.cs.uiuc.edu/~jeffe/pubs/linsat.html).
Jeffε
CC BY-SA 3.0
2014-04-12T01:27:06.680Z
2014-04-12T01:27:06.680Z
Jeffε
<p>The title is a little misleading: but hopefully the question isn't:</p>

<p><a href="http://arxiv.org/abs/1404.0799">Grønlund and Pettie's new result</a> showing that <a href="http://en.wikipedia.org/wiki/3SUM">3SUM</a> has only $O(n^{3/2})$ <a href="http://en.wikipedia.org/wiki/Decision_tree_model">decision tree complexity</a> got me wondering: </p>

<blockquote>
  <p>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)$ ? </p>
</blockquote>

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

CC BY-SA 3.0
2014-04-12T01:31:59.827Z
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.
Jeffε
CC BY-SA 3.0
2014-04-12T03:09:43.793Z
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.
Robin Kothari
CC BY-SA 3.0
2014-04-12T18:15:49.623Z
Maybe I should have said 'example of a simple problem' instead :).
Suresh Venkat
<cc.complexity-theory><machine-models><decision-trees>
Provable gaps between decision tree complexity and "true" complexity
Suresh Venkat
# Provable gaps between decision tree complexity and "true" complexity

(Asked by: username_0 on 2014-04-11)

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

[Grønlund and Pettie's new result](http://arxiv.org/abs/1404.0799) showing that [3SUM](http://en.wikipedia.org/wiki/3SUM) has only $O(n^{3/2})$ [decision tree complexity](http://en.wikipedia.org/wiki/Decision_tree_model) 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 ?

**Tags:** cc.complexity-theory, machine-models, decision-trees

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: Maybe I should have said 'example of a simple problem' instead :).  

---

## 2 answers

### Answer by username_1 on 2014-04-12. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_0**: If I wanted to be REALLY PEDANTIC I'd point out that being NP-hard is not a firm lower bound. but that's a good example of the spirit of what I'm looking for.  
> **username_1**: Yeah, but we don't know how to prove firm lower bounds.  
> **username_4**: @JɛﬀE Do you maybe know of a nice write up or exposition of this result? I find the original very hard to follow, some definitions are not clear at all to me.  
> **username_1**: At least the basic definitions are described in [my paper on linear degeneracy problems](http://www.cs.uiuc.edu/~jeffe/pubs/linsat.html).  

---

### Answer by username_3 on 2014-04-15. Score: 5

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).

> **Comments:**
> **username_4**: Let me disagree a bit. In the RAM model, we do not necessarily need to read the whole input. In the Turing machine model, there are many trivial problems that can be solved faster with a decision-tree (or on a RAM machine). Also see Robin's comment to the original question.  

---

