1
$\begingroup$

This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could modify a list were by swapping the contents of consecutive indices, then it would take at least quadratic time to sort a list in the worst case, regardless of what we can do to individual characters. This is because it takes at least $\Omega(n^2)$ adjacent transpositions to express a general element in $S_n$.

In a decision tree lower bound, we are concerned with the complexity of making a sequence of choices. For example, in the comparison model of sorting, it takes at least $\Omega(n \log n)$ time to sort a list, regardless of how powerful our list-manipulation primitives are. (Note that I am using these terms somewhat loosely; e.g., a "pebbling lower bound" does not have to refer to an actual pebble game.)

Notice that these two types of lower bound are dual in some sense. In particular, pebbling lower bounds are exclusively concerned with the complexity of constructing the output from input, but ignore the complexity of "decision making." On the other hand, decision tree lower bounds are exclusively concerned with the complexity of decision making, and ignore the complexity of actually constructing the output.

My question is is there any lower bound which uses both pebbling and decision tree techniques, such that either one alone would be insufficient? I know of exactly one, in a paper by Tiuryn (A simplified proof of DDL < DL, 1989.)

(Note that I am by no means saying that these two types exhaust all forms of lower bounds. For example, neither of them use the effectiveness of computation.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.