Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
3  
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. –  JɛffE Apr 12 at 1:31
8  
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 Apr 12 at 3:09
    
Maybe I should have said 'example of a simple problem' instead :). –  Suresh Venkat Apr 12 at 18:15

2 Answers 2

up vote 15 down vote accepted

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.

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

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

share|improve this answer
2  
Thanks, and welcome to Theoretical Computer Science ! –  Suresh Venkat Apr 15 at 17:25
    
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 Apr 15 at 17:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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