<p>The natural model related to decision trees that simulates RAMs without loss is the branching program.  Basically, it is a decision tree with common subtrees coalesced yielding a DAG.   Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program.  (You might need to use multi-way branching.)</p>

<p>For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input.  Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.)    For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits on a RAM.) Is that the form of your problem?</p>

<p>You seem to suggest that you are using the # of outputs to try to get a larger lower bound.   However, even with this you also can compute any function with height = # inputs and space = # input bits.  (Read and remember the input, and output all the values required at each leaf node.  It is usual to allow multiple outputs at a single node.)   </p>

CC BY-SA 2.5
2011-01-30T15:05:20.777Z
Maybe it's better for the author to merge this answer with the previous one since they're almost identical.
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-30T14:41:56.273Z
2011-01-30T14:41:56.273Z
Paul Beame
<p>The natural model related to decision trees that can simulates RAMs is the branching program.  Basically, it is a decision tree with common subtrees coalesced yielding a DAG.   Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program.  (You might need to use multi-way branching.)</p>

<p>For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input.  Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.)    For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits.  Is that the form of you problem?</p>

<p>You seem to suggest that you are using the # of outputs to try to get a larger lower bound.  It is usual for multi-output problems to allow many outputs along a single edge rather than at leaf nodes (see, for example, Borodin-Cook's 1982 paper on sorting lower bounds).  However, even without this assumption, one also can compute any function with height = # inputs and space = # input bits.  (Read and remember the input, and output all the values at each leaf node.)</p>

CC BY-SA 2.5
2011-01-30T12:15:12.133Z
Thank you for your answer. The input of the problem is a collection of set of integers, so that it can be supposed that they are given as lists. Anyway, thank you for pointing out Borodin and Cook's technique (I didn't know it at all). I hope that kind of method can be applied to my problem.
Totoro
CC BY-SA 2.5
2011-01-30T05:10:20.540Z
2011-01-30T05:10:20.540Z
Paul Beame
<p>I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be <em>partially</em> generalized to the random access machine model. By <em>partially</em>, I mean a generalization to RAM programs with a certain time/space tradeoff. For instance, I'd like to show that my problem cannot be solved by a linear-time and -space RAM program.</p>

<p>A.M. Ben-Amram and Z. Galil proved in this <a href="http://portal.acm.org/citation.cfm?id=146666">paper</a> that a RAM program running in time $t$ and space $s$ can be simulated in $O(t \, \log s)$ time on a pointer machine. Do we know similar results which could be applied to decision trees? </p>

<p>Alternatively, is it possible to simulate a RAM program running in space $s$ with a decision tree of degree $s$? (intuitively, indirect addressing could be simulated using nodes of degree $\leq s$)</p>

CC BY-SA 2.5
2011-01-28T19:06:50.130Z
I don't know too much about classical query complexity (decision tree complexity) but when working in the analogous model in a quantum setting (quantum query complexity) you sometimes get pretty poor lower bounds for the circuit model. For instance, for HSP you can show that the query complexity is polynomial, but the unitaries between queries take an exponential number of gates... and as far as we suspect the general HSP is not doable in polynomial time, so query complexity gives only very loose lower bounds. Or are you fine with a very loose lower bound?
Artem Kaznatcheev
CC BY-SA 2.5
2011-01-28T19:58:10.413Z
Actually, I'd really like to get a superlinear lower bound for (some) programs running on RAM. That's why I hoped that restricting the space complexity could help.
Totoro
CC BY-SA 2.5
2011-01-29T06:10:27.207Z
I do not understand your question. How can you have a quadratic lower bound on query complexity? Also, time-space tradeoffs often use direct product theorems, so you might have to work harder to get such results.
Hartmut Klauck
CC BY-SA 2.5
2011-01-29T10:04:29.153Z
The complexity lower bound in the decision tree model comes from a lower bound on the number of possible outputs of the problem (whose logarithm provides a lower bound on the height on the tree).
Totoro
<cc.complexity-theory><lower-bounds>
Complexity lower bound: the gap between decision trees and RAMs
Totoro
# Complexity lower bound: the gap between decision trees and RAMs

(Asked by: username_0 on 2011-01-28)

I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be *partially* generalized to the random access machine model. By *partially*, I mean a generalization to RAM programs with a certain time/space tradeoff. For instance, I'd like to show that my problem cannot be solved by a linear-time and -space RAM program.

A.M. Ben-Amram and Z. Galil proved in this [paper](http://portal.acm.org/citation.cfm?id=146666) that a RAM program running in time $t$ and space $s$ can be simulated in $O(t \, \log s)$ time on a pointer machine. Do we know similar results which could be applied to decision trees?

Alternatively, is it possible to simulate a RAM program running in space $s$ with a decision tree of degree $s$? (intuitively, indirect addressing could be simulated using nodes of degree $\leq s$)

**Tags:** cc.complexity-theory, lower-bounds

> **Comments:**
> **username_1**: I don't know too much about classical query complexity (decision tree complexity) but when working in the analogous model in a quantum setting (quantum query complexity) you sometimes get pretty poor lower bounds for the circuit model. For instance, for HSP you can show that the query complexity is polynomial, but the unitaries between queries take an exponential number of gates... and as far as we suspect the general HSP is not doable in polynomial time, so query complexity gives only very loose lower bounds. Or are you fine with a very loose lower bound?  
> **username_0**: Actually, I'd really like to get a superlinear lower bound for (some) programs running on RAM. That's why I hoped that restricting the space complexity could help.  
> **username_2**: I do not understand your question. How can you have a quadratic lower bound on query complexity? Also, time-space tradeoffs often use direct product theorems, so you might have to work harder to get such results.  
> **username_0**: The complexity lower bound in the decision tree model comes from a lower bound on the number of possible outputs of the problem (whose logarithm provides a lower bound on the height on the tree).  

---

## 2 answers

### Answer by username_3 on 2011-01-30. Score: 10 | Accepted answer

The natural model related to decision trees that can simulates RAMs is the branching program. Basically, it is a decision tree with common subtrees coalesced yielding a DAG. Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program. (You might need to use multi-way branching.)

For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input. Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.) For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits. Is that the form of you problem?

You seem to suggest that you are using the # of outputs to try to get a larger lower bound. It is usual for multi-output problems to allow many outputs along a single edge rather than at leaf nodes (see, for example, Borodin-Cook's 1982 paper on sorting lower bounds). However, even without this assumption, one also can compute any function with height = # inputs and space = # input bits. (Read and remember the input, and output all the values at each leaf node.)

> **Comments:**
> **username_0**: Thank you for your answer. The input of the problem is a collection of set of integers, so that it can be supposed that they are given as lists. Anyway, thank you for pointing out Borodin and Cook's technique (I didn't know it at all). I hope that kind of method can be applied to my problem.  

---

### Answer by username_3 on 2011-01-30. Score: 1

The natural model related to decision trees that simulates RAMs without loss is the branching program. Basically, it is a decision tree with common subtrees coalesced yielding a DAG. Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program. (You might need to use multi-way branching.)

For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input. Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.) For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits on a RAM.) Is that the form of your problem?

You seem to suggest that you are using the # of outputs to try to get a larger lower bound. However, even with this you also can compute any function with height = # inputs and space = # input bits. (Read and remember the input, and output all the values required at each leaf node. It is usual to allow multiple outputs at a single node.)

> **Comments:**
> **username_4**: Maybe it's better for the author to merge this answer with the previous one since they're almost identical.  

---

