7
$\begingroup$

This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms:

  1. The best query algorithm: this algorithm uses the minimal number of queries and then optimizes to reduce total time, while preserving queries (this has query complexity $Q_1$ and time complexity $T_1$).
  2. The best time algorithm: this algorithm uses the minimal amount of time and then optimized to reduce total queries, while preserving time (this has query complexity $Q_2$ and time complexity $T_2$).

We saw that for partial functions, we can have arbitrarily large seperations between $T_1$ and $T_2$ and $Q_1$ and $Q_2$. However, this approach only works for partial functions.

For total functions, we can use the approach in this question to show that $T_1 \in O(n!2^n T_2)$ and for queries we can show $Q_2 \in O(2^{Q_1})$. Thus for total functions there seems to be a bound on the total separation. Can we improve it? Or come up with total functions with provable separations?

(We have a potential candidate for a separation in this answer but no provable results)

$\endgroup$
  • $\begingroup$ How do you use the fact stated in question 7563 to relate T1 to T2 and Q2 to Q1? Although I vaguely get the idea, I fail to see the details and in particular I fail to understand why the same approach would not work for partial functions. $\endgroup$ – Tsuyoshi Ito Nov 3 '11 at 20:20
  • $\begingroup$ @TsuyoshiIto It won't work for partial functions, because you won't know which leafs to prune from the decision tree. If you have another algorithm with some running time T3 that decides if a given input is in the domain or not of the partial function, then the approach would work, but you would need $T_2 + T_3$ instead of just $T_3$ as a factor. In other words, in the first approach Robin, Joe, and I used all the magic is hidden in the partial-ness of the function. (Sorry for the slow response) $\endgroup$ – Artem Kaznatcheev Nov 8 '11 at 16:04
  • $\begingroup$ my bad, there is a typo in my above response, it should say "instead of just $T_2$". It would look like $O(n!2^n(T_2 + T_3))$ $\endgroup$ – Artem Kaznatcheev Nov 8 '11 at 16:50
1
$\begingroup$

Here is a sketch of an attempt at partial separation. I was trying to improve this over the past two weeks into a full answer, but haven't made much progress. Hopefully someone else knows how to extend it.

Let

\[f_{n,m}: \{0,1\}^n \times \{0,1\}^{{m \choose 2}} \rightarrow \{0,1\}\]

So we have a total function on tuples.

$f_{n,m}(x,y)$ returns $1$ if $x = 1^n$ and if $y$ interpreted as the edges of a graph has a clique or independent graph of size $n$. Otherwise, it returns $0$.

Thus if $R_n$ is the $n$-th diagonal Ramsey number then for $m \geq R_n$ and all $y \in \{0,1\}^{{m \choose 2}}$ we have $f(1^n,y) = 1$. Thus, if we can compute $R_n$ on an input of $1^n$ then we don't have to read the bits of $y$ if $m$ is large enough, and the query complexity of the query-optimal algorithm drops to $n$.

However, $R_n$ is harder to compute on an input of $1^n$ than it is to check if a graph given by edges $y$ has a clique of independent set of size $n$ on input $(1^n,y)$. Thus, a time-optimal algorithm can't afford to compute $R_n$. It could, instead use some approximation $\tilde{R}_n > R_n$. For $m < \tilde{R}_n$ a time-optimal algorithm will read at least some bits of $y$.

Thus, for $R_n \leq m < \tilde{R}_n$ the query-optimal algorithm will use more time to make fewer queries than the time-optimal algorithm.

This approach can be made slightly less hand-wavy (or generalized to other Ramsey-like problems) but I think even the more rigorous attempt doesn't fully answer the question.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.