A note on zero error algorithms having oracle access to one NP query

Abstract

It is known that S2p ⊆ ZPPNP [3]. The reverse direction of whether ZPPNP is contained in S 2p 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 S2p. That is, we prove that ZPPNP[1] ⊆ S2p. © Springer-Verlag Berlin Heidelberg 2005.