15
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Artem Kaznatcheev ♦
    Jan 28, 2011 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – Totoro
    Jan 28, 2011 at 19:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hartmut Klauck
    Jan 29, 2011 at 6:10
  • 1
    $\begingroup$ 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). $\endgroup$
    – Totoro
    Jan 29, 2011 at 10:04

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Totoro
    Jan 30, 2011 at 12:15
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Maybe it's better for the author to merge this answer with the previous one since they're almost identical. $\endgroup$
    – Oleksandr Bondarenko
    Jan 30, 2011 at 15:05

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.