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)$.

  • 1
    $\begingroup$ Interesting question. Can I ask what is your motivation? $\endgroup$ Aug 6 '15 at 17:50
  • $\begingroup$ 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. $\endgroup$ 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.

See also https://cstheory.stackexchange.com/q/31482 for more information about this class.

  • 1
    $\begingroup$ 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}}$. $\endgroup$ May 12 '17 at 9:11

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.