How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues?

Each queue is FIFO. Time refers to the number of operations on the queues.

There are different formal models for the queues, but an answer in any of the following models would be interesting (models listed in the order of increasing difficulty of proving the lower bound):
1. Shuffle only: Each item is a black box.
2. Shuffle+copy: Each item is a black box that can be copied and deleted.
3. Linear network coding: Items can be xor-ed but are otherwise black boxes.
4. An item has $O(\log n)$ bits; we have a state machine of our choosing with $n^{O(1)}$ states.
5. An item is 1 bit, and we have a state machine with $O(2^{n^c})$ states ($c < 1$).
6. Same as (5), but we only have the decision problem (palindrome).
7. Same as (6), but we are nondeterministic.

As this question notes, a list can be reversed using two queues in time $O(n \log n)$, but the accepted answer did not prove optimality. More generally, $k > 1$ queues (with $O(k)$ items in local memory) can be used to sort a list with $O(n \log n / \log k)$ queue operations.

The reason I expect the $Ω(n \log n)$ lower bound in this question is that processing using queues essentially shuffles items, and a list cannot be reversed using $o(\log n)$ riffle shuffles since each shuffle at most halves the length of each ascending sequence. Intuitively, after $o(n \log n)$ queue operations, most of the list will still have a mostly unshuffled feel, but I do not know how to formalize and prove it. One attempt is to assign to a sorted subsequence of length $m$ score $m \mathrm{lg} m$, with the total score being the maximum sum of scores across disjoint subsequences; I conjecture that in (1), the total score changes by at most $O(n)$ after $O(n)$ operations. For (3)-(7) (above), the lack of shuffling will need to be complemented with a communication complexity argument.

Model (5) may look powerful, but even it cannot implement a stack with $o(n^{(1-c)/k})$ amortized time per operation where $k$ is the number of queues (as my answer to this question can be modified to show). However, data structure lower bounds (even when amortized) are often qualitatively different from (and easier than) superlinear optimal running time lower bounds.

For (7), it is enough to consider two queues, since two queues are known to nondeterministically simulate $O(1)$-queues in linear time by keeping the computation path in one queue, and doing $k$ passes to check the consistency of all $k$ queues (and by repeating the construction, it sufficies that for one of the queues, all reads happen after all writes).


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.