On zero error algorithms having oracle access to one query

It is known that $${\rm S}_{2}^{p} \subseteq {\rm ZPP}^{NP}$$ (Cai, 2001). The reverse direction of whether ZPPNP is contained in $${\rm S}_{2}^{p}$$ remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and random string), then it can be simulated in $${\rm S}_{2}^{p}$$ . That is, we prove that $${\rm S}_{2}^{p}$$ . Next we consider whether the above result can be improved as $${\rm ZPP}^{NP[1]} \subseteq {\rm P}^{NP}$$ and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPPNP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ PNP, settling a long standing open problem. We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely, we prove that $${\rm ZPP}^{\Sigma_{2}^{p}[1]} \subseteq {\rm P}^{\Sigma_{2}^{p}[2]}$$ . On the other hand, by adapting our proof of our main result it can be shown that $${\rm ZPP}^{\Sigma_{2}^{p}[1]} \subseteq {\rm S}_{2}^{\rm NP[1]}$$ . For the purpose of comparing these two results, we prove that $${\rm P}^{\Sigma_{2}^{p}} \subseteq {\rm S}_{2}^{\rm NP[1]}$$ . We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2, $${\rm ZPP}^{\Sigma_{k}^{p}[1]} \subseteq {\rm P}^{\Sigma_{k}^{p}[2]}$$ and $${\rm P}^{\Sigma_{k}^{p}} \subseteq {\rm S}_{2}^{\Sigma_{k-1}^{p}[1]}$$ .