14
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Apr 12, 2014 at 1:31
  • 9
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Apr 12, 2014 at 3:09
  • $\begingroup$ Maybe I should have said 'example of a simple problem' instead :). $\endgroup$
    – Suresh Venkat
    Apr 12, 2014 at 18:15

2 Answers 2

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Apr 12, 2014 at 3:09
  • 5
    $\begingroup$ Yeah, but we don't know how to prove firm lower bounds. $\endgroup$
    – Jeffε
    Apr 12, 2014 at 14:05
  • $\begingroup$ @JɛffE 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. $\endgroup$
    – domotorp
    Apr 16, 2014 at 15:05
  • 1
    $\begingroup$ At least the basic definitions are described in my paper on linear degeneracy problems. $\endgroup$
    – Jeffε
    Apr 16, 2014 at 18:25
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Apr 15, 2014 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.