Trade off between time and query complexity

Question

Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query takes at least one unit step, and computations between queries are counted as free, time complexity is as at least as high as query complexity. However, can we say anything about the separations?

I am curious about work in the classical, or quantum literature, but provide examples from QC since I am more familiar.

Some famous algorithms such as Grover’s search and Shor’s period finding, the time complexity is within poly-logarithmic factors of the query complexity. For others, such as the Hidden Subgroup Problem, we have polynomial query complexity, yet polynomial time algorithms are not known.

Since a gap potentially exists between time and query complexity, it is not clear that an optimal time complexity algorithm has to have the same query complexity as the optimal query complexity algorithm.

Are there examples of trade-offs between time and query complexity?

Are there problems where the best known time complexity algorithm has a different query complexity than the best known query complexity algorithm? In other words, can we perform more queries to make the between-query operations easier?

Or is there an argument that shows that there is always a version of an asymptotically optimal query algorithm having an implementation with asymptotically best time-complexity?

Answer 1

Here's an attempt at creating an artificial function with the following property:

• The problem can be solved with $O(\log n)$ queries, but requires $\exp(n)$ time.
• The problem can be solved with $O(n)$ time but that requires $O(n)$ queries

Let the input size be $n + \log n$. Let the first $\log n$ bits (let's call this string x) encode the input to a problem complete for EEXP. The next $n$ bits (let's call this string y) have the property that they are all zero if and only if x is a NO instance of the EEXP-complete problem.

In words, the first $\log n$ bits encode a hard problem, and the next $n$ bits give you a clue about the solution of the problem. However, to figure out the solution by looking at the $n$ bit string you make $\Omega(n)$ queries.

So this problem can be solved by either reading only the first $\log n$ bits and spending exp(n) time or by reading $n$ bits and using only linear time.

The same function goes through for quantum query complexity.. insert square root signs where necessary.

Answer 2

A more extreme version of Robin's example:

Let the input size be $n$, with the first $n-1$ bits (call this string $x$) encoding a Turing machine $T_x$. Fix some function $f(n)$. Let the last bit of the string be $1$ iff the Turing machine $T_x$ halts in less than $f(n)$ steps. The problem is then to determine if $T_x$ halts in less than $f(n)$ steps and the parity of $x$ is even.

Thus, by making $n-1$ queries the problem can be solved in time $O(f(n))$, while by making $n$ queries, the problem can be solved in time $O(n)$.

Answer 3

I like Robin Kothari's answer and Joe Fitzsimons' modification. In an obvious extension of their answers they can achieve any separation ratio (except constant-vs.-non-constant) between the smaller and bigger query complexity and bigger and smaller time complexity. However, there is no obvious way to make their functions non-partial. I want to point out a natural problem where we have a separation and show that big separations are harder for total functions.

---

A natural problem

Ben Reichardt pointed out by email the formula-evaluation problem. The quantum query complexity for evaluating a general read-once AND-OR formula on $n$ variables is $\Theta(\sqrt{n})$. However, the $O(\sqrt{n})$-query algorithm is not time efficient. Here, the fastest known algorithm is shown to make $O(\sqrt{n}\log{n})$ queries and run in time polylogarithmically worse. Thus we have a natural total problem where there is a known separation. Although there is no proof that this separation has to exist.

Total functions are harder to separate?

To me, it seems like it is harder to find total functions with provable seperations. To show that the case of total and partial functions is different, I will provide an argument on the largest separation between the query complexities of the query-optimal and time-optimal algorithms for a total function.

Using Simon's [1] lower bound we can see that if a function depends on $m$ of its variables, we will need to query at-least $\Omega{(\log m)}$ of them. On the other hand, the most we would ever query is $m$. Note that there is no reason to query all $n$ variables, because the output is independent of $n - m$ of them (call those dead bits) and for a total function no secret structure will be revealed by looking at those dead bits. Thus even the most time-optimal algorithm for a total function can be modified to use at most $m$ queries by simply assuming that the dead bits are all $0$.

Therefore if we write $(\text{query complexity}\; , \; \text{time complexity})$, then for a total function, given the query-optimal algorithm with complexity $(q_1(n),t_1(n))$, there is a time-optimal algorithm with complexity $(q_2(n),t_2(n))$ with $q_2(n) \leq f(q_1(n))$ and $f(n) = O(2^n)$. In other words, we can't have more than an exponential separation in query complexity between the query-optimal and time-optimal algorithms for total functions. I would not be surprised if these really loose bounds could be improved.

[1] H.U. Simon, "A tight Z(loglogn)-bound on the time for parallel RAM’s to compute non-degenerate Boolean functions", in: Symp. on Foundations of Computation Theory, Lecture Notes in Computer Science, Vol. 158, Springer, Berlin, 1983, pp. 439–444.