Equivalence in adaptive vs non-adaptive queries in complexity

43 Views Asked by At

I am working on the following problem from Complexity by Ashcroft:

We say that an algorithm $A$ makes non-adaptive queries to an oracle if it selects all of the strings on which it will query the oracle before querying the oracle on any of those strings (in other words, the queries to the oracle can be thought of as being carried out "in parallel" the choice of later query strings can't depend on the answers that the oracle provides to earlier queries). In contrast, an adaptive oracle algorithm makes its queries sequentially (in particular, the choice of some $i$-th query string for the oracle can depend on the answers that the oracle gave to query strings $1,\ldots,i−1$). Show that a language $L$ is decided by a deterministic polynomial-time algorithm that has nonadaptive access to an NP oracle, if and only if $L$ is decided by a deterministic polynomial-time algorithm that has adaptive access to an NP oracle but can make only $O(\log{n})$ queries.

This is my attempt:

Suppose there exists a deterministic polynomial-time algorithm $D$ that decides $L$ using non-adaptive queries to an NP oracle. Let $n$ be the size of the input to $D$. Let $D$ makes at most $m = O(p(n))$ non-adaptive queries, where $p(n)$ is a polynomial. We can create an adaptive algorithm $D'$ as follows:

  1. Run $D$ until the point where it would make its non-adaptive queries to the NP oracle.
  2. Enumerate all the $m$ queries that $D$ would make and sort them into a binary search tree.
  3. Query the oracle adaptively using binary search to find whether each query string is in the NP language. This takes $O(\log m)$ queries per original query.
  4. Use the oracle's answers to proceed with the rest of the algorithm $D$.

Because $m = O(p(n))$, $O(\log m) = O(\log p(n)) = O(\log n)$ when $p(n)$ is polynomial. Thus, $D'$ uses $O(\log n)$ queries.

On the other hand, suppose we have a deterministic polynomial-time algorithm $D''$ that decides $L$ using $O(\log n)$ adaptive queries to an NP oracle. We can construct a non-adaptive algorithm $D'''$ as follows:

  1. Simulate $D''$ up to its first oracle query.
  2. For each possible answer from the NP oracle for this query (Yes/No), fork the simulation of $D''$ into two branches.
  3. Continue this process recursively for each branch up to $O(\log n)$ depth, essentially exploring the complete binary tree of possible oracle responses.
  4. Use these responses to run $D''$ to its conclusion in each branch, which will give the correct answer for $L$ in at least one branch.

This creates a total of $O(2^{\log n}) = O(n)$ branches, which can be run in parallel as non-adaptive queries. Therefore, $D'''$ is a deterministic polynomial-time algorithm that decides $L$ using non-adaptive queries.

By proving both directions, we establish the equivalence.

I wanted to ask whether this makes sense. I feel some of my arguments are a stretch (eg. where I conclude $D'$ uses $O(\log n)$ queries), and if there's a better way to do this that is more informative, I would appreciate it.