# Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a witness query $q$ to $\phi$ returns a witness $y \leq 2^{p(n)}$ satisfying $\varphi(q,y)$, if such exists, and returns $2^{p(n)} + 1$, otherwise.

Question: Let $f$ be a function in $FP^{\Sigma^p_1}[wit]$, i.e. $f$ is computed by a polynomial time Turing machine $M$ that makes polynomially many witness queries to a $\Sigma^p_1$ oracle $\phi(q) \equiv \exists y \leq 2^{p(n)} \varphi(q,y)$. My question is the following: Can we somehow construct a polynomial time Turing machine $M_1$ which makes polynomially many witness queries to $\phi(q)$ in parallel (i.e. all the queries to $\phi$ come first, then the sequence of replies to the queries come after) and such that $M^{\phi}_1(x) = M^{\phi}(x)$.

• Interesting question. Can I ask what is your motivation? Aug 6 '15 at 17:50
• Ioannis, I was working on some problem where I needed to make use of the kind of complexity class above. However, in my case, it was easy to construct the machine $M_1$ from a machine $M$ computing a certain function. So, I just happened to ask myself the question above. Aug 10 '15 at 13:44

By a standard argument that also applies in this case, polynomially parallel many witness queries give the same power as $O(\log n)$ many sequential witness queries: $$\mathrm{FP^{\|\Sigma^P_1[wit]}=FP^{\Sigma^P_1[wit,\log]}}.$$ In particular, the predicates (i.e., 0–1 valued functions) in $\mathrm{FP^{\Sigma^P_1[wit]}}$ are exactly those from $\Delta^P_2=\mathrm{P^{NP}}$, whereas predicates in $\mathrm{FP^{\|\Sigma^P_1[wit]}}$ are exactly those from the complexity class $\Theta^P_2=\mathrm{P^{NP[\log]}=P^{\|NP}=L^{NP}}$ (see zoo). It is widely expected that $\Theta^P_2\ne\Delta^P_2$, and this is supported by oracle separation results. Thus, the answer to your question should be no.
• Also note that with polynomially many unrestricted queries, witnessing is redundant, as one can compute a witness with polynomially many ordinary NP queries by binary search: $\mathrm{FP^{\Sigma^P_1[wit]}=FP^{\Sigma^P_1}}$. May 12 '17 at 9:11